专栏首页温安适的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步骤 ,直到队列为空为止。

图解说明

核心代码

/**
  * 无权最短路径
  * 
  * @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);
			}
		  }
	    }
     }
   }
}

该算法的时间界限

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步骤,直到所有顶点的最短路径都已知。

图解说明

核心代码

     /**
	 * 著名的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. 直到队列为空为止

核心代码

	/**
	 * 有权有负值最短路径
	 * 借助广度优先搜素
	 * @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());
						}
					}
				}
			}
		}
	}

时间界限

O(|E|*|V|)

总结与补充

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

完整代码地址

码云地址

无权无圈最短路径

有权无负值最短路径

有权有负值最短路径

github地址

无权无圈最短路径

有权无负值最短路径

有权有负值最短路径

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • mysql-innodb-事务

    InnoDB存储引擎层产生,物理日志,记录的是对页的修改,innodb1.2版本后,最大512GB

    温安适
  • 冲突管理感悟

    从1月计划考试开始,到6月中下旬,我都在复习PMP考试。尽管付出了不少时间,然而仍然不敢保证100%通过。但是在学习的过程中,PMBOK中的知识,却对我造成了极...

    温安适
  • 写给自己-Hystrix断路器是如何工作的

    20181130,Hystrix已经不再维护,这里是学习记录。12月1日才完成,没有完成11月的诺言,捐款记录以上动弹。

    温安适
  • 关键路径法

    林万程
  • 第五届SDN大赛初赛部分试题解题思路:基于ONOS的路径反转实现

    作者简介:周正强,北京邮电大学未来网络实验室在读研究生,个人邮箱:857538065@qq.com

    SDNLAB
  • 极客资源丨那些被“慕课网”偷偷藏起来的“真·免费教程”!

    一川水巷
  • VBA复制当前路径的所有文件到指定文件夹

    当前路径 = ThisWorkbook.Path & "\*.*" '如果只复制xls则把 "*.*" 改成 "*.xls"

    巴西_prince
  • uniapp 打包h5问题

    河湾欢儿
  • 这可能是史上最全的Python算法集!

    其主要特点有以下三点:选择了在实践中广泛应用的算法;依赖最少;容易阅读,容易理解每个算法的基本思想。希望阅读本文后能对你有所帮助。

    AI科技大本营
  • 收藏 | 一文洞悉Python必备50种算法(附解析)

    其主要特点有以下三点:选择了在实践中广泛应用的算法;依赖最少;容易阅读,容易理解每个算法的基本思想。希望阅读本文后能对你有所帮助。

    用户2769421

扫码关注云+社区

领取腾讯云代金券