贪婪算法-单源最短路径
前言
感谢每一位朋友的阅读与建议，今天对最短路径blog进行了修改，调整图和部分内容。感谢各位关注。提早祝大家圣诞节平安快乐。
单源最短路径问题描述
给定一个带权有向图G=（V,E），其中每条边的权是一个实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到其他所有各顶点的最短路径长度。这里的长度就是指路上各边权之和。这个问题通常称为单源最短路径问题
1.无权最短路径（非唯一）
算法分析
- 由于图没有权，所以我们只需要关注路径上的边
- 无权最短路径实质上是特殊的有权最短路径，因为我们可以将每条边按权为1处理。
- 我们可以一层一层处理，先找与s距离为1的节点，之后找距离为2的节点，直到所有节点都被访问到。 注： 按层搜索图的方式，称为广度优先搜索，这种搜索方式类似树的层序遍历。
算法描述
借助队列实现每条边只访问一次。
- 初始情况下声明所有节点的最短路径未知
- 起点s声明最短路径为0，并将s入队。
- 从队列中移除一个节点v ，并更新该点v的临接表wlist中每一个临接点w的最短路径为当前最短路径dv+1
- 重复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算法描述
- 选择一个未知最短路径的节点v，它在所有未知最短路径的节点集中有最小的路径dv。
- 声明v为已知最短路径节点
- 更新v的临接顶点集，针对每个v的临接点w，若dv+cvw<dw，则更新w的路径。 注：cvw为边(v，w)的权，dv,dw分别为v,w的最短路径
- 重复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算法
- Dijkstra有可能过早的声明一个节点的最短路径已知，由于有权有负值存在，可能还有一条含有负值边的路径经过该节点，使得该节点的最短路径更小。
- 利用一个修正值，将图的边修正为正数之后使用Dijkstra，也是不行的 ，因为含有较多边的路径会被过度修正，如下图所示：
图解说明“修正负值出现的问题”
有权有负值无圈最短路径的解法
借助广度优先搜素实现。
- 将起点放入队列
- 从队列中取出节点v，更新v的临接顶点集，针对每个v的临接点w，若dv+cvw<dw，则更新w的路径。 注：cvw为边(v，w)的权，dv,dw分别为v,w的最短路径
- 当w不在队列中时，将w放入队列
- 直到队列为空为止
核心代码
/**
* 有权有负值最短路径
* 借助广度优先搜素
* @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|)总结与补充
- 上述算法，若图有圈，都不能执行，上述算法是以临接表的方式标示图的。
- 无权最短路径借助广度优先搜素实现，其时间界限为：
O(|E|+|V|)- Dijkstra是解决有权无负值图单源最短路径的经典算法。
- 若权有负值，借助广度优先搜素与有权无负值最短路径思想结合来解决 ，其时间界限为：
O(|E|*|V|)完整代码地址
码云地址
github地址
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
