最短路算法详解（Dijkstra 算法，Bellman-Ford 算法，Floyd-Warshall 算法）
文章目录
- 一、Dijkstra 算法
- 二、Bellman-Ford 算法
- 三、Floyd-Warshall 算法
由于文章篇幅有限，下面都只给出算法对应的部分代码，需要全部代码调试参考的请点击： 图的源码
最短路径问题：从在带权图的某一顶点出发，找出一条通往另一顶点的最短路径，最短也就是沿路径各边的权值总和达到最小。涉及到三个算法：
- 单源最短路径：Dijkstra 算法（迪杰斯特拉算法）（不能解决负权图）
- 单源最短路径：Bellman-Ford 算法（贝尔曼-福特算法）（可以解决负权图）
- 多源最短路径：Floyd-Warshall 算法（弗洛伊德算法）（可以解决负权图）
注意：本文采用的图是邻接矩阵实现的。
一、Dijkstra 算法
- 算法概括：
Dijkstra 是一种求解非负权图上单源最短路径的算法。
- 算法流程：
其过程为：将结点分成两个集合，已确定最短路长度的点集（记为 S 集合）和未确定最短路长度的点集（记为 T 集合）。一开始所有的点都属于 T 集合。
需要对 dist 数组（存储最短路的长度）进行初始化，除了起点设置为 0 外，其它的都设置为无穷大。
接着重复如下操作：
- 从 T 集合中，选取一个最短路长度最小的节点，移动到 S 集合中。
- 对那些刚刚加入 S 集合的结点的所有出边执行
松弛操作。
直到 T 集合为空，算法结束。
- 时间复杂度：
每次确定一个顶点 O（n），并松弛其连接出去的所有边（最多有 n - 1条），其时间复杂度为 O（n ^ 2）。
松弛操作：
对于起点 B 到达点 A，松弛操作对应如下的式子：dis(A) = min(dis(A) , dis(C ) + 边 CA），当确定一个顶点的最短路径后，对其连出去的所有边进行松弛操作。
过程演示如下图：
- 代码如下：
/**
* @param vSrc 起点
* @param dist 存储从起点到各个顶点的最小权值
* @param pPath 存储各个顶点到起点的最短权值路径
*/
public void dijkstra(char vSrc, int[] dist, int[] pPath) {
//用来标记已经确定的点
boolean[] vis = new boolean[size];
//获取起点对应下标
int srcIndex = getVIndex(vSrc);
//初始化 dist 和 pPath
Arrays.fill(dist, Integer.MAX_VALUE);
Arrays.fill(pPath, -1);//最终结果为 -1 说明起点到达不了
//起点到起点为 0
dist[srcIndex] = 0;
pPath[srcIndex] = srcIndex;
//填写 dist
for (int i = 0; i < size; i++) {//一共要填写 size 次
//确定一条最短的路径
int min = Integer.MAX_VALUE;
int u = srcIndex;
for (int v = 0; v < size; v++) {
if (vis[v] == false && min > dist[v]) {
min = dist[v];
u = v;
}
}
vis[u] = true;
//进行松弛操作 + 填写 pPath
//一个顶点出度最大为 size，把不存在的排除即可
for (int v = 0; v < size; v++) {
if (vis[v] == false && matrix[u][v] != Integer.MAX_VALUE && dist[u] + matrix[u][v] < dist[v]) {
dist[v] = dist[u] + matrix[u][v];
pPath[v] = u;
}
}
}
}
- 测试 Dijkstra 算法：
通过打印最短路的顶点组成和最短路的长度，即可验证正确性。
public void printShortPath(char vSrc,int[] dist,int[] pPath) {
int srcIndex = getIndexOfV(vSrc);
int n = arrayV.length;
for (int i = 0; i < n; i++) {
//i下标正好是起点 则不进行路径的打印
if(i != srcIndex) {
ArrayList<Integer> path = new ArrayList<>();
int pathI = i;
while (pathI != srcIndex) {
path.add(pathI);
pathI = pPath[pathI];
}
path.add(srcIndex);
Collections.reverse(path);
for (int pos : path) {
System.out.print(arrayV[pos]+" -> ");
}
System.out.println(dist[i]);
}
}
}
public static void testGraphDijkstra() {
String str = "syztx";
char[] array = str.toCharArray();
GraphByMatrix g = new GraphByMatrix(str.length(),true);
g.initArrayV(array);
g.addEdge('s', 't', 10);
g.addEdge('s', 'y', 5);
g.addEdge('y', 't', 3);
g.addEdge('y', 'x', 9);
g.addEdge('y', 'z', 2);
g.addEdge('z', 's', 7);
g.addEdge('z', 'x', 6);
g.addEdge('t', 'y', 2);
g.addEdge('t', 'x', 1);
g.addEdge('x', 'z', 4);
int[] dist = new int[array.length];
int[] parentPath = new int[array.length];
g.dijkstra('s', dist, parentPath);
g.printShortPath('s', dist, parentPath);
}
运行结果为：
构建的图为过程演示时的图。
显然正确🎉🎉🎉
二、Bellman-Ford 算法
- 算法概括：
Bellman–Ford 算法是一种基于松弛操作的最短路算法，可以求出有负权的图的最短路，并可以对最短路不存在的情况进行判断。
- 算法流程：
Bellman–Ford 算法所做的，就是不断尝试对图上每一条边进行松弛。我们每进行一轮循环，就对图上所有的边都尝试进行一次松弛操作，当一次循环中没有成功的松弛操作时，算法停止。
- 时间复杂度：
在最短路存在的情况下，由于一次松弛操作会使最短路的边数至少 + 1，而最短路的边数最多为 n - 1，因此整个算法最多执行 n - 1 轮松弛操作。故总时间复杂度为 O（n * m）。其中 n 为顶点个数，m 为 边的个数。
- 代码如下：
/**
*
* @param vSrc 起点
* @param dist 存储从起点到各个顶点的最小权值
* @param pPath 存储各个顶点到起点的最短权值路径
* @return 返回 true 表示该图不存在负权回路，返回 false 表示该图存在负权回路
*/
public boolean bellmanFord(char vSrc, int[] dist, int[] pPath) {
//获取顶点下标
int srcIndex = getVIndex(vSrc);
//初始化数据
Arrays.fill(dist, Integer.MAX_VALUE);
Arrays.fill(pPath, -1);
dist[srcIndex] = 0;
pPath[srcIndex] = srcIndex;
//松弛操作
//进行 size 次
for (int k = 0; k < size; k++) {
//遍历每条边
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (matrix[i][j] != Integer.MAX_VALUE && dist[i] + matrix[i][j] < dist[j]) {
dist[j] = dist[i] + matrix[i][j];
pPath[j] = i;
}
}
}
}
//判断是否存在负回路
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (matrix[i][j] != Integer.MAX_VALUE && dist[i] + matrix[i][j] < dist[j]) {
return false;//存在负回路
}
}
}
return true;//不存在负回路
}
- 测试 Bellman-Ford 算法：
下面的测试案例就是根据这张图进行设计的。
public static void testGraphBellmanFord() {
String str = "syztx";
char[] array = str.toCharArray();
GraphByMatrix g = new GraphByMatrix(str.length(), true);
g.initArrayV(array);
for (int i = 0; i < str.length(); i++) {
Arrays.fill(g.matrix[i], Integer.MAX_VALUE);
}
//负权回路实例
// g.addEdge('s', 't', 6);
// g.addEdge('s', 'y', 7);
// g.addEdge('y', 'z', 9);
// g.addEdge('y', 'x', -3);
// g.addEdge('y', 's', 1);
// g.addEdge('z', 's', 2);
// g.addEdge('z', 'x', 7);
// g.addEdge('t', 'x', 5);
// g.addEdge('t', 'y', -8);
// g.addEdge('t', 'z', -4);
// g.addEdge('x', 't', -2);
//不存在负权回路的情况
g.addEdge('s', 't', 6);
g.addEdge('s', 'y', 7);
g.addEdge('y', 'z', 9);
g.addEdge('y', 'x', -3);
g.addEdge('z', 's', 2);
g.addEdge('z', 'x', 7);
g.addEdge('t', 'x', 5);
g.addEdge('t', 'y', 8);
g.addEdge('t', 'z', -4);
g.addEdge('x', 't', -2);
int[] dist = new int[array.length];
int[] parentPath = new int[array.length];
boolean fig = g.bellmanFord('s', dist, parentPath);
if (fig) {
g.printShortPath('s', dist, parentPath);
} else {
System.out.println("存在负权回路");
}
}
运行结果如下：
三、Floyd-Warshall 算法
- 算法概括：
Floyd-Warshall 算法是用来求任意两个结点之间的最短路的。适用于任何图，不管有向无向，边权正负，但是最短路必须存在（不能有个负环） ，复杂度比较高。
- 算法流程：
Floyd-Warshall 算法的原理是动态规划。
设 D(i,j,k) 为从 i 到 j 的只以(1…k)集合中的节点为中间节点的最短路径的长度。
- 若最短路径不经过 k，则 D(i,j,k) = D(i,j,k - 1)。
- 若最短路径经过 k，则 D(i,j,k) = D(i,k,k - 1) + D(k,j,k - 1)。（k - 1 不影响起点和终点取 k）
因此，D(i,j,k) = min(D(i,j,k - 1)，D(i,k,k - 1) + D(k,j,k - 1))。
在实际算法中，为了节省空间，可以直接在原来空间上进行迭代，这样空间可降至二维。
- 时间复杂度：
k 的取值从 1 到 n，每次 k 都要进行一次完整的动态规划。时间复杂度为 O（n ^ 3）。
- 代码如下：
/**
*
* @param dist 存储各个顶点之间的最小权值
* @param pPath 存储各个顶点之间的最短权值路径
*/
public void floyWarShall(int[][] dist, int[][] pPath) {
//初始化
for (int i = 0; i < size; i++) {
Arrays.fill(dist[i], Integer.MAX_VALUE);
Arrays.fill(pPath[i], -1);
}
//将边填入到 dist 数据，给后续动态规划初始化
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
//存在边
if (matrix[i][j] != Integer.MAX_VALUE) {
dist[i][j] = matrix[i][j];
pPath[i][j] = i;
//边不存在的情况
} else {
pPath[i][j] = -1;
}
if (i == j) {
dist[i][j] = 0;
pPath[i][j] = -1;
}
}
}
//动态规划
for (int k = 0; k < size; k++) {
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE &&
dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
pPath[i][j] = pPath[k][j];
}
}
}
}
//下面的代码为测试代码，打印 dist，和 pPath
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (dist[i][j] == Integer.MAX_VALUE) {
System.out.print(" * ");
} else {
System.out.print(dist[i][j] + " ");
}
}
System.out.println();
}
System.out.println("=========打印路径==========");
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
System.out.print(pPath[i][j] + " ");
}
System.out.println();
}
System.out.println("=================");
}
- 测试 Floyd-Warshall 算法：
测试图例如下：
public static void testGraphFloydWarShall() {
String str = "12345";
char[] array = str.toCharArray();
GraphByMatrix g = new GraphByMatrix(str.length(), true);
g.initArrayV(array);
//没有边，设置为 最大值。
for (int i = 0; i < g.size; i++) {
Arrays.fill(g.matrix[i], Integer.MAX_VALUE);
}
g.addEdge('1', '2', 3);
g.addEdge('1', '3', 8);
g.addEdge('1', '5', -4);
g.addEdge('2', '4', 1);
g.addEdge('2', '5', 7);
g.addEdge('3', '2', 4);
g.addEdge('4', '1', 2);
g.addEdge('4', '3', -5);
g.addEdge('5', '4', 6);
int[][] dist = new int[array.length][array.length];
int[][] parentPath = new int[array.length][array.length];
g.floyWarShall(dist, parentPath);
for (int i = 0; i < array.length; i++) {
g.printShortPath(array[i],dist[i],parentPath[i]);
}
}
运行结果如下：
下图为测试图例的过程图。
通过对比可以发现，我们的运行结果是正确的（路径会差 1，因为下标是从 0 开始的）。
参考资料：OI-wiki。
结语：
其实写博客不仅仅是为了教大家，同时这也有利于我巩固知识点，和做一个学习的总结，由于作者水平有限，对文章有任何问题还请指出，非常感谢。如果大家有所收获的话还请不要吝啬你们的点赞收藏和关注，这可以激励我写出更加优秀的文章。
