前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >贪婪算法-单源最短路径

贪婪算法-单源最短路径

作者头像
温安适
发布2018-05-17 16:46:56
1.1K0
发布2018-05-17 16:46:56
举报
文章被收录于专栏:温安适的blog

前言

感谢每一位朋友的阅读与建议,今天对最短路径blog进行了修改,调整图和部分内容。感谢各位关注。提早祝大家圣诞节平安快乐。

单源最短路径问题描述

给定一个带权有向图G=(V,E),其中每条边的权是一个实数。另外,还给定V中的一个顶点,称为源。现在要计算从源到其他所有各顶点的最短路径长度。这里的长度就是指路上各边权之和。这个问题通常称为单源最短路径问题

1.无权最短路径(非唯一)

算法分析

  1. 由于图没有权,所以我们只需要关注路径上的边
  2. 无权最短路径实质上是特殊的有权最短路径,因为我们可以将每条边按权为1处理。
  3. 我们可以一层一层处理,先找与s距离为1的节点,之后找距离为2的节点,直到所有节点都被访问到。 注: 按层搜索图的方式,称为广度优先搜索,这种搜索方式类似树的层序遍历。

算法描述

借助队列实现每条边只访问一次。

  1. 初始情况下声明所有节点的最短路径未知
  2. 起点s声明最短路径为0,并将s入队。
  3. 从队列中移除一个节点v ,并更新该点v的临接表wlist中每一个临接点w的最短路径为当前最短路径dv+1
  4. 重复1-3步骤 ,直到队列为空为止。

图解说明

核心代码

代码语言:javascript
复制
/**
  * 无权最短路径
  * 
  * @param s 起点
  */
public void unweight(Vertex s) {
	Queue<Vertex> q = new LinkedList<Vertex>();
	for (Vertex x : graph) {
	 //每个节点的初始最短路径为Integer的最大值,表示该节点的最短路径未知
	  x.setDist(Integer.MAX_VALUE);
	}
	s.dist = 0;
	q.add(s);
	while (!q.isEmpty()) {
		Vertex v = q.poll();
	  if (v != null) {
		if (v.getAdj() != null && !v.getAdj().isEmpty()) {
		  for (Vertex w : v.getAdj()) {
			if (w.getDist() == Integer.MAX_VALUE) {//每条边只访问一次
				w.setDist(v.getDist()+1);
				w.setPath(v);
				q.add(w);
			}
		  }
	    }
     }
   }
}

该算法的时间界限

代码语言:javascript
复制
O(|E|+|V|)

2.有权无负值最短路径

Dijkstra算法是解决有权无负值单源最短路径的经典算法。

Dijkstra算法描述

  1. 选择一个未知最短路径的节点v,它在所有未知最短路径的节点集中有最小的路径dv。
  2. 声明v为已知最短路径节点
  3. 更新v的临接顶点集,针对每个v的临接点w,若dv+cvw<dw,则更新w的路径。 注:cvw为边(v,w)的权,dv,dw分别为v,w的最短路径
  4. 重复1-3步骤,直到所有顶点的最短路径都已知。

图解说明

核心代码

代码语言:javascript
复制
     /**
	 * 著名的dijkstra算法 解决单源最短路径(权无负值)
	 * 
	 * @param s
	 *            起点
	 */
public void dijkstra(Vertex s) {
	for (Vertex v : graph) {// 初始默认所有顶点未被访问
		v.setDist(Integer.MAX_VALUE);
		v.known = false;
	}
	s.dist = 0;// 声明起点的距离为0
	PriorityQueue<Vertex> priorityQueue = new PriorityQueue<Vertex>();
	// 将s放入优先队列
	priorityQueue.add(s);
	while (!priorityQueue.isEmpty()) {// 知道所有顶点的最短路径都已知并且优先队列为空
		Vertex v = priorityQueue.poll();// 取出未知节点中最短路径最小的节点
		if (v != null) {
			if (!v.known) {
				v.known = true;// 声明该节点已知
				if (v.getAdj() != null && !v.getAdj().isEmpty()) {
				// 如 dv+cvw<=dw 则更新临接点的最短路径,并且更新值放入到优先队列中
				for (AdjVertex adjW : v.getAdj()) {
				if (!adjW.getW().known) {
					if (v.dist + adjW.cvw < adjW.getW().getDist()) {
					  adjW.getW().setDist(v.dist + adjW.cvw);
					  adjW.getW().setPath(v);
					  priorityQueue.add(adjW.getW());
								}
							}
						}
					}
				}
			}
		}
	}

3.有权有负值无圈最短路径(非唯一)

问题定义

针对一个有权图,该图的权有负值,使用某个顶点s作为输入参数,找出该顶点s到其他顶点的最短距离。

为何不能使用Dijkstra算法

  1. Dijkstra有可能过早的声明一个节点的最短路径已知,由于有权有负值存在,可能还有一条含有负值边的路径经过该节点,使得该节点的最短路径更小。
  2. 利用一个修正值,将图的边修正为正数之后使用Dijkstra,也是不行的 ,因为含有较多边的路径会被过度修正,如下图所示:

图解说明“修正负值出现的问题”

有权有负值无圈最短路径的解法

借助广度优先搜素实现。

  1. 将起点放入队列
  2. 从队列中取出节点v,更新v的临接顶点集,针对每个v的临接点w,若dv+cvw<dw,则更新w的路径。 注:cvw为边(v,w)的权,dv,dw分别为v,w的最短路径
  3. 当w不在队列中时,将w放入队列
  4. 直到队列为空为止

核心代码

代码语言:javascript
复制
	/**
	 * 有权有负值最短路径
	 * 借助广度优先搜素
	 * @param s 起点
	 */
	public void weightNegative(Vertex s) {
		Queue<Vertex> q = new LinkedList<Vertex>();
		for (Vertex v : graph) {
			v.dist = Integer.MAX_VALUE;
			v.isInQueue = false;
		}
		s.dist = 0;
		s.isInQueue = true;
		q.add(s);
		while (!q.isEmpty()) {
			Vertex v = q.poll();
			v.isInQueue = false;
			if (v.getAdj() != null && !v.getAdj().isEmpty()) {
				for (AdjVertex wadj : v.getAdj()) {
					if (wadj.cvw + v.dist < wadj.getW().dist) {
						wadj.getW().setDist(wadj.cvw + v.dist);
						wadj.getW().setPath(v);
						if (!wadj.getW().isInQueue) {
							wadj.getW().isInQueue = false;
							q.add(wadj.getW());
						}
					}
				}
			}
		}
	}

时间界限

代码语言:javascript
复制
O(|E|*|V|)

总结与补充

  1. 上述算法,若图有圈,都不能执行,上述算法是以临接表的方式标示图的。
  2. 无权最短路径借助广度优先搜素实现,其时间界限为:
代码语言:javascript
复制
O(|E|+|V|)
  1. Dijkstra是解决有权无负值图单源最短路径的经典算法。
  2. 若权有负值,借助广度优先搜素与有权无负值最短路径思想结合来解决 ,其时间界限为:
代码语言:javascript
复制
O(|E|*|V|)

完整代码地址

码云地址

无权无圈最短路径

有权无负值最短路径

有权有负值最短路径

github地址

无权无圈最短路径

有权无负值最短路径

有权有负值最短路径

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 前言
  • 单源最短路径问题描述
  • 1.无权最短路径(非唯一)
    • 算法分析
      • 算法描述
        • 图解说明
        • 核心代码
        • 该算法的时间界限
      • 2.有权无负值最短路径
        • Dijkstra算法描述
        • 图解说明
        • 核心代码
      • 3.有权有负值无圈最短路径(非唯一)
        • 问题定义
        • 为何不能使用Dijkstra算法
        • 图解说明“修正负值出现的问题”
        • 有权有负值无圈最短路径的解法
        • 核心代码
        • 时间界限
    • 总结与补充
    • 完整代码地址
      • 码云地址
        • github地址
        领券
        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档