前言
- 最短路径的算法有两个,Dijkstra算法 和 Floyd算法。
- Dijkstra算法 解决的是 单源 最短路径问题。
- Floyd算法解决的是 多源 最短路径问题,并且可以处理负权图。
- 今天要讲的就是Dijkstra算法。
- 加:
feng--Insist
(大写的i),进java交流群讨论互联网+技术。可索要PPT等资料。 - 其他资料,建议先看本篇博客。:Dijkstra算法和Floyd算法:https://blog.csdn.net/weixin_43872728/article/details/100662957
- 代码位置:https://github.com/fengfanli/dataStructuresAndAlgorithm/tree/master/src/com/feng/algorithm/self_learn
一、单源最短路径
1、单源最短路径问题
-
解决的问题: 求解单源最短路径,即各个节点到达源点的最短路径或权值。如下图中
考察其他所有节点到源点的最短路径和长度 - 局限性: 无法解决权值为负数的情况
- 资料
- 可先看匹配视频:https://www.bilibili.com/video/BV1o44y1B7NM/
- 代码:待上传。
2、Dijkstra 初始化
首先已知的是:
给定 邻接矩阵表示的图Graph、源点S、终点T。
a、参数
参数:
参数名 | 解释 |
---|---|
S | 记录当前已经处理过的源点到最短节点 |
U | 记录还未处理的节点 |
dist[] | 记录各个节点到起始节点的最短权值 |
path[] | 记录各个节点的上一级节点(用来联系该节点到起始节点的路径) |
b、初始化参数
- 顶点集S: 节点A到自已的最短路径长度为0。只包含源点,即S={A},代码中没有这个,这里是为了步骤清晰而设置的。
- 顶点集U: 包含除A外的其他顶点. 即U={B,C,D,E,F,G}
- dist[]: 源点还不能到达的节点,其权值为∞
名 | A | B | C | D | E | F | G |
---|---|---|---|---|---|---|---|
dist[]: | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
初始化值: | 0 | 4 | 6 | 6 | ∞ | ∞ | ∞ |
path[]: 记录当前节点的前驱节点下标(源点还不能到达的节点为-1)
名 | A | B | C | D | E | F | G |
---|---|---|---|---|---|---|---|
path[]: | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
初始化值: | 0 | 0 | 0 | 0 | -1 | -1 | -1 |
c、算法步骤
- 初始化:设定除源节点以外的其它所有节点到源节点的距离为INFINITE(一个很大的数),且这些节点都没被处理过。如上图所示
- 从源节点出发,更新相邻节点(图中为B、C、D)到源节点的距离。然后在所有节点中选择一个最段距离的点作为当前节点。
- 标记当前节点为done(表示已经被处理过),与步骤2类似,更新其相邻节点的距离。(这些相邻节点的距离更新也叫
松弛
,目的是让它们与源节点的距离最小。因为你是在当前最小距离的基础上进行更新的,由于当前节点到源节点的距离已经是最小的了,那么如果这些节点之前得到的距离比这个距离大的话,我们就更新它)。 - 步骤3做完以后,设置这个当前节点已被done,然后寻找下一个具有最小代价(cost)的点,作为新的当前节点,重复步骤3.
- 如果最后检测到目标节点时,其周围所有的节点都已被处理,那么目标节点与源节点的距离就是最小距离了。如果想看这个最小距离所经过的路径,可以回溯,前提是你在步骤3里面加入了当前节点的最优路径前驱节点信息。
- 我总结了下可用如下几句话代替:
两步走- 从dist[]中在集合U中的选择最小距离加入到S中,作为当前节点。(最小距离:就是 当前节点到源点的最小距离)
-
遍历当前节点的邻边节点:更新dist[]和path[]
- 如果经过当前节点+邻边权重 < 邻边节点,则改变dist[]和path[],否者不改变。
3、Dijkstra 算法详细步骤
a、第一轮算法执行
-
如上图,因为dist[]中排出掉集合U中节点,最小值是4,也就是节点B,所以将B纳入到集合S中(圈中)。
-
首先 在dist[]数组中并在集合U中 最小值是节点B,既当前节点,其邻边有C和E,所以看是否要更新C和E。
- 节点C:因为
C的最小距离dist[1](B的最小距离)4+1(B到C的距离)=5 < dist[2](C的最小距离) = 6
,所以 dist[2]=5,path[2]=1 - 节点E:因为
E的最小距离 dist[1](B的最小距离)4+7(B到E的距离)=11 < dist[4] (E的最小距离)=无穷大
,所以 dist[4]=11,path[4]=1
- 节点C:因为
-
第一轮算法两个邻边节点C、E有改变
b、第二轮算法执行
- 如上图,因为dist[]中排出掉集合U中节点,最小值是5,也就是节点C,所以将C纳入到集合S中(圈中)。
- 首先在dist[]数组中并在集合U中 最小值是节点C,既当前节点,其邻边有E和F,所以看是否要更新E和F。
- 节点E:因为
C的最小距离 dist[2](也就是C的最小距离)5+6(C到E的距离)=11 == dist[4](E的最小距离) = 11
,所以不动 - 节点F:因为
F的最小距离 dist[2](也就是C的最小距离)5+4(C到F的距离)=9 < dist[5] (F的最小距离)=无穷大
,所以 dist[5]=9,path[5]=2
- 节点E:因为
- 第二轮算法两个邻边节点仅有 F有改变
c、第三轮算法执行
- 如上图,因为dist[]中排出掉集合U中节点,最小值是6,也就是节点D,所以将D纳入到集合S中(圈中)。
- 首先在dist[]数组中并在集合U中 最小值是节点D,既当前节点,其邻边有C和F,所以看是否要更新C和F。
- 节点C:因为
C的最小距离 dist[3](也就是D的最小距离)6+2(D到C的距离)=8 > dist[2](C的最小距离) = 5
,所以不动 - 节点F:因为
F的最小距离 dist[3](也就是D的最小距离)6+5(D到F的距离)=11 > dist[5] (F的最小距离)=9
,所以不动 - 第三轮算法两个邻边节点C、F都没有改变
d、第四轮算法执行
- 如上图,因为dist[]中排出掉集合U中节点,最小值是9,也就是节点F,所以将F纳入到集合S中(圈中)。
- 首先在dist[]数组中并在集合U中 最小值是节点F,既当前节点,其邻边有E和G,所以看是否要更新E和G 。
- 节点E:因为
E的最小距离 dist[5](也就是F的最小距离) 9 +1(F到E的距离)=10 < dist[4](E的最小距离) =11
,所以 dist[4] = 10,path[4]=5 - 节点G:因为
G的最小距离 dist[5](也就是F的最小距离) 9 +8(F到G的距离)=17 < dist[6](G的最小距离) =无穷大
,所以 dist[6]=17,path[6]=5 - 第四轮算法两个邻边节点E、G都有改变
e、第五轮算法执行
- 如上图,因为dist[]中排出掉集合U中节点,最小值是9,也就是节点F,所以将F纳入到集合S中(圈中)。
- 首先在dist[]数组中并在集合U中 最小值是节点E,既当前节点,其邻边有G,所以看是否要更新G 。
- 节点G:因为
G的最小距离 dist[4](也就是E的最小距离) 10 +6(E到G的距离)=16 < dist[6](G的最小距离) =17
,所以 dist[6]=16,path[6]=4 - 第五轮算法邻边 节点G有改变
f、第六轮算法执行
- 如上图,因为dist[]中排出掉集合U中节点,最小值是16,也就是节点G,所以将G纳入到集合S中(圈中)。
- 首先在dist[]数组中并在集合U中 最小值是节点G,既当前节点,其没有邻边。
- 第六轮算法邻边节点G没有改变
- 到此算法遍历结束
4、java算法实现
给定矩阵表示的Graph结构。输入源点v0和终点v1。文章来源:https://www.toymoban.com/news/detail-672285.html
二、多源最短路径
1、多源最短路径问题
- 上面的Dijkstra 解决的是单源最短路径的问题,首先要给定 开始节点和终止结点,如果换了开始和终止节点,那就要每次都要重新跑一次。
- 那就引出了多源最短路径问题:就是执行一次算法,求出每两个点之间的最短距离,这就是多源最短路径算法。这个算法代码略简单一些。
- 思想只有一个:要算两个点之间的最短距离,就看有没有第三个点使得
2、Floyd初始化
首先已知的是:
给定 **邻接矩阵表示的图Graph。文章来源地址https://www.toymoban.com/news/detail-672285.html
a、参数
参数名 | 解释 |
---|---|
A[][] | 函数中的参数,需要返回,存储的是节点的前置节点。 |
path[][] | 存储的是每两点之间的所需距离。 |
b、参数初始化
参数名 | 解释 |
---|---|
A[][] | 就是图的赋值,从代码中可以看出,比较简单 |
path[][] | 默认都是-1.表示从A点到B点是直达的。 |
c、算法步骤
- 对于每个顶点
v
(体现在代码的第一层for循环),和任意一顶点(i,j)
(体现代码的第二、三层循环),切i!=j、v!=i、v!=j
。 - 如果
A[i][j] > A[i][v] + A[]v[j]
,则将A[i][j] 更新为 A[i][v] + A[v][j]
的值,并且将path[i][j]改为v
。
3、Floyd算法详细步骤
4、java 算法实现
package com.feng.algorithm.self_learn.floyd.floyd1;
/**
* 学习视频:https://www.bilibili.com/video/BV1LE411R7CS
*/
public class FloydAlgorithm {
public static void main(String[] args) {
int[][] graph = new int[4][4];
int N = Short.MAX_VALUE;
graph[0] = new int[]{0, 5, N, 7};
graph[1] = new int[]{N, 0, 4, 2};
graph[2] = new int[]{3, 3, 0, 2};
graph[3] = new int[]{N, N, 1, 0};
int[][] path = new int[4][4];
int[][] A = Floyd.floyd(graph, path);
int u = 1;
int v = 0;
Floyd.printPath(u, v, path);
System.out.println();
System.out.println(u + "->" + v +" shortest path is :" + A[u][v]);
}
}
class Floyd {
/**
* 佛洛依德算法,给定邻接矩阵表示的图,
* path[][]:存放路径中间的节点,如果是-1就是直达
* A[][]:存放任意两个节点之间的距离
* 举例:从1-0,从A得出距离是6,从path得出 1-3-2-0
* @param graph
* @param path
*/
static int[][] floyd(int[][] graph, int[][] path) {
int n = graph.length;
int v, i, j;
int[][] A = new int[n][n];
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
A[i][j] = graph[i][j];
path[i][j] = -1;
}
}
for (v = 0; v < n; v++) {
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (A[i][j] > A[i][v] + A[v][j]) {
A[i][j] = A[i][v] + A[v][j];
path[i][j] = v;
}
}
}
}
return A;
}
/**
* 递归打印路径
* @param u
* @param v
* @param path
*/
static void printPath(int u, int v, int[][] path) {
if (path[u][v] == -1) { // 如果等于 -1 。说明就是直达的
System.out.printf(u + "->" + v + " ");
} else {
int mid = path[u][v];
printPath(u, mid, path);
printPath(mid, v, path);
}
}
}
到了这里,关于数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!