弗洛伊德算法求最短路径

在一个加权图中，如果想找到各个顶点之间的最短路径，可以考虑使用弗洛伊德算法。

弗洛伊德算法既适用于无向加权图，也适用于有向加权图。使用弗洛伊德算法查找最短路径时，只允许环路的权值为负数，其它路径的权值必须为非负数，否则算法执行过程会出错。

弗洛伊德算法的实现思路

弗洛伊德算法是基于动态规划算法实现的，接下来我们以在图 1 所示的有向加权图中查找各个顶点之间的最短路径为例，讲解弗洛伊德算法的实现思路。

图 1 有向加权图

图 1 中不存在环路，且所有路径（边）的权值都为正数，因此可以使用弗洛伊德算法。

弗洛伊德算法查找图 1 中各个顶点之间的最短路径，实现过程如下：

1) 建立一张表格，记录每个顶点直达其它所有顶点的权值：

表 1 各个顶点直达路径的权值

起始顶点指的是从哪个顶点出发，目标顶点指的是要达到的顶点，例如 2->1 路径的权值是 2，顶点 2 是起始顶点，顶点 1 是目标顶点。此外，∞ 表示无穷大的数，即顶点之间不存在直达的路径。

2) 在表 1 的基础上，将顶点 1 作为 "中间顶点"，计算从各个顶点出发途径顶点 1 再到达其它顶点的权值，如果比表 1 中记录的权值更小，证明两个顶点之间存在更短的路径，对表 1 进行更新。

从各个顶点出发，途径顶点 1 再到达其它顶点的路径以及对应的权值分别是：

• 2-1-3：权值为 2 + ∞ = ∞，表 1 中记录的 2-3 的权值也是 ∞；
• 2-1-4：权值为 2 + 5 = 7，表 1 中记录的 2-4 的权值是 4；
• 3-1-2：权值为 ∞ + 3，表 1 中记录的 3-2 的权值是 1；
• 3-1-4：权值为 ∞ + 5，表 1 中记录的 3-4 的权值是 ∞；
• 4-1-2：权值为 ∞ + 3，表 1 中记录的 4-2 的权值是 ∞；
• 4-1-3：权值为 ∞ + ∞，表 1 中记录的 4-3 的权值是 2。

以上所有的路径中，没有比表 1 中记录的权值最小的路径，所以不需要对表 1 进行更新。

3) 在表 1 的基础上，以顶点 2 作为 "中间顶点"，计算从各个顶点出发途径顶点 2 再到达其它顶点的权值：

• 1-2-3：权值为 3 + ∞，表 1 中记录的 1-3 的权值为 ∞；
• 1-2-4：权值为 3 + 4 = 7，表 1 中 1-4 的权值为 5；
• 3-2-1：权值为 1 + 2 = 3，表 1 中 3-1 的权值为 ∞，3 < ∞；
• 3-2-4：权值为 1 + 4 = 5，表 1 中 3-4 的权值为 ∞，5 < ∞；
• 4-2-1：权值为 ∞ + 2，表 1 中 4-1 的权值为 ∞；
• 4-2-3：权值为 ∞ + ∞，表 1 中 4-3 的权值为 2。

以顶点 2 作为 "中间顶点"，我们找到了比 3-1、3-4 更短的路径，对表 1 进行更新：

表 2 更新后的 "表 1"

4) 在表 2 的基础上，将顶点 3 作为 "中间顶点"，计算从各个顶点出发途径顶点 3 再到达其它顶点的权值：

• 1-3-2 权值为 ∞ + 1，表 2 中 1-2 的权值为 3；
• 1-3-4 权值为 ∞ + 5，表 2 中 1-4 的权值为 5；
• 2-3-1 权值为 ∞ + 3，表 2 中 2-1 的权值为 2；
• 2-3-4 权值为 ∞ + 5，表 2 中 2-4 的权值为 4；
• 4-3-1 权值为 2 + 3 = 5，表 2 中 4-1 的权值为 ∞，5 < ∞；
• 4-3-2 权值为 2 + 1 = 3，表 2 中 4-2 的权值为 ∞，3 < ∞；

以顶点 3 作为 "中间顶点"，我们找到了比 4-1、4-2 更短的路径，对表 2 进行更新：

表 3 更新后的 "表 2"

5) 在表 3 的基础上，将顶点 4 作为 "中间顶点"，计算从各个顶点出发途径顶点 4 再到达其它顶点的权值：

• 1-4-2 权值为 5 + 3 = 8，表 3 中 1-2 的权值为 3；
• 1-4-3 权值为 5 + 2 = 7，表 3 中 1-3 的权值为 ∞，7 < ∞；
• 2-4-1 权值为 4 + 5 = 9，表 3 中 2-1 的权值为 2；
• 2-4-3 权值为 4 + 2 = 6，表 3 中 2-3 的权值为 ∞，6 < ∞；
• 3-4-1 权值为 4 + 5 = 9，表 3 中 3-1 的权值为 3；
• 3-4-2 权值为 5 + 5 = 10 ，表 3 中 3-2 的权值为 1。

以顶点 4 作为 "中间顶点"，我们找到了比 1-3、2-3 更短的路径，对表 3 进行更新：

表 4 更新后的 "表 3"

通过将所有的顶点分别作为“中间顶点”，最终得到的表 4 就记录了各个顶点之间的最短路径。例如，4-1 的最短路径为 4-3-2-1。

弗洛伊德算法的具体实现

了解了弗洛伊德算法查找最短路径的实现思路后，接下来仍以图 1 为例，分别编写 C、Java、Python 程序实现弗洛伊德算法。

如下是用弗洛伊德算法查找图 1 中各顶点之间最短路径的 C 语言程序：

1. #include <stdio.h>
2. #define V 4    //设定图中的顶点数
3. #define INF 65535   // 设置一个最大值
4. int P[V][V] = { 0 }; //记录各个顶点之间的最短路径
5. void printMatrix(int matrix[][V]);  //输出各个顶点之间的最短路径
6. void printPath(int i, int j); // 递归输出各个顶点之间最短路径的具体线路
7. void floydWarshall(int graph[][V]); // 实现弗洛伊德算法
8. 
   
9. int main() {
10. // 有向加权图中各个顶点之间的路径信息
11. int graph[V][V] = { {0, 3, INF, 5},
12. {2, 0, INF, 4},
13. {INF, 1, 0, INF},
14. {INF, INF, 2, 0} };
15. floydWarshall(graph);
16. }
17. // 中序递归输出各个顶点之间最短路径的具体线路
18. void printPath(int i, int j)
19. {
20. int k = P[i][j];
21. if (k == 0)
22. return;
23. printPath(i, k);
24. printf("%d-", k + 1);
25. printPath(k, j);
26. }
27. // 输出各个顶点之间的最短路径
28. void printMatrix(int graph[][V]) {
29. int i, j;
30. for (i = 0; i < V; i++) {
31. for (j = 0; j < V; j++) {
32. if (j == i) {
33. continue;
34. }
35. printf("%d - %d: 最短路径为:", i + 1, j + 1);
36. if (graph[i][j] == INF)
37. printf("%s\n", "INF");
38. else {
39. printf("%d", graph[i][j]);
40. printf("，依次经过：%d-", i + 1);
41. //调用递归函数
42. printPath(i, j);
43. printf("%d\n", j + 1);
44. }
45. }
46. }
47. }
48. // 实现弗洛伊德算法,graph[][V] 为有向加权图
49. void floydWarshall(int graph[][V]) {
50. int  i, j, k;
51. //遍历每个顶点，将其作为其它顶点之间的中间顶点，更新 graph 数组
52. for (k = 0; k < V; k++) {
53. for (i = 0; i < V; i++) {
54. for (j = 0; j < V; j++) {
55. //如果新的路径比之前记录的更短，则更新 graph 数组
56. if (graph[i][k] + graph[k][j] < graph[i][j]) {
57.                    graph[i][j] = graph[i][k] + graph[k][j];
58. //记录此路径
59.                    P[i][j] = k;
60. }
61. }
62. }
63. }
64. // 输出各个顶点之间的最短路径
65. printMatrix(graph);
66. }

如下是用弗洛伊德算法查找图 1 中各顶点之间最短路径的 Java 程序：

1. public class Floyd {
2. static int V = 4; // 顶点的个数
3. static int[][] P = new int[V][V]; // 记录各个顶点之间的最短路径
4. static int INF = 65535; // 设置一个最大值
5. 
   
6. // 中序递归输出各个顶点之间最短路径的具体线路
7. public static void printPath(int i, int j) {
8. int k = P[i][j];
9. if (k == 0)
10. return;
11. printPath(i, k);
12.        System.out.print((k + 1) + "-");
13. printPath(k, j);
14. }
15. 
    
16. // 输出各个顶点之间的最短路径
17. public static void printMatrix(int[][] graph) {
18. for (int i = 0; i < V; i++) {
19. for (int j = 0; j < V; j++) {
20. if (j == i) {
21. continue;
22. }
23.                System.out.print((i + 1) + " - " + (j + 1) + "：最短路径为:");
24. if (graph[i][j] == INF)
25.                    System.out.println("INF");
26. else {
27.                    System.out.print(graph[i][j]);
28.                    System.out.print("，依次经过：" + (i + 1) + "-");
29. // 调用递归函数
30. printPath(i, j);
31.                    System.out.println((j + 1));
32. }
33. }
34. }
35. }
36. 
    
37. // 实现弗洛伊德算法,graph[][V] 为有向加权图
38. public static void floydWarshall(int[][] graph) {
39. int i, j, k;
40. // 遍历每个顶点，将其作为其它顶点之间的中间顶点，更新 graph 数组
41. for (k = 0; k < V; k++) {
42. for (i = 0; i < V; i++) {
43. for (j = 0; j < V; j++) {
44. // 如果新的路径比之前记录的更短，则更新 graph 数组
45. if (graph[i][k] + graph[k][j] < graph[i][j]) {
46.                        graph[i][j] = graph[i][k] + graph[k][j];
47. // 记录此路径
48.                        P[i][j] = k;
49. }
50. }
51. }
52. }
53. // 输出各个顶点之间的最短路径
54. printMatrix(graph);
55. }
56. 
    
57. public static void main(String[] args) {
58. // 有向加权图中各个顶点之间的路径信息
59. int[][] graph = new int[][] { { 0, 3, INF, 5 }, { 2, 0, INF, 4 }, { INF, 1, 0, INF }, { INF, INF, 2, 0 } };
60. floydWarshall(graph);
61. }
62. }

如下是用弗洛伊德算法查找图 1 中各顶点之间最短路径的 Python 程序：

1. V = 4   # 顶点的个数
2. INF = 65535    # 设定一个最大值
3. P = [[0]*V for i in range(V)] # 记录各个顶点之间的最短路径
4. # 有向加权图中各个顶点之间的路径信息
5. graph = [[0, 3, INF, 5],
6. [2, 0, INF, 4],
7. [INF, 1, 0, INF],
8. [INF, INF, 2, 0]]
9. # 中序递归输出各个顶点之间最短路径的具体线路
10. def printPath(i,j):
11.    k = P[i][j]
12. if k == 0:
13. return;
14. printPath(i , k)
15. print("%d-" % (k + 1) , end='')
16. printPath(k , j)
17. # 输出各个顶点之间的最短路径
18. def printMatrix(graph):
19. for i in range(V):
20. for j in range(V):
21. if j == i:
22. continue
23. print("%d - %d: 最短路径为:"%(i + 1, j + 1) , end='')
24. if graph[i][j] == INF:
25. print("INF")
26. else:
27. print(graph[i][j] , end='')
28. print("，依次经过：%d-"%(i+1) , end='')
29. # 调用递归函数
30. printPath(i , j)
31. print(j + 1)
32. # 实现弗洛伊德算法,graph[][V] 为有向加权图
33. def floydWarshall(graph):
34. # 遍历每个顶点，将其作为其它顶点之间的中间顶点，更新 graph 数组
35. for k in range(V):
36. for i in range(V):
37. for j in range(V):
38. # 如果新的路径比之前记录的更短，则更新 graph 数组
39. if graph[i][k] + graph[k][j] < graph[i][j]:
40.                    graph[i][j] = graph[i][k] + graph[k][j]
41. # 记录此路径
42.                    P[i][j] = k
43. # 输出各个顶点之间的最短路径
44. printMatrix(graph)
45. 
    
46. floydWarshall(graph)

以上程序的输出结果均为：

1 - 2: 最短路径为:3，依次经过：1-2

1 - 3: 最短路径为:7，依次经过：1-4-3

1 - 4: 最短路径为:5，依次经过：1-4

2 - 1: 最短路径为:2，依次经过：2-1

2 - 3: 最短路径为:6，依次经过：2-4-3

2 - 4: 最短路径为:4，依次经过：2-4

3 - 1: 最短路径为:3，依次经过：3-2-1

3 - 2: 最短路径为:1，依次经过：3-2

3 - 4: 最短路径为:5，依次经过：3-2-4

4 - 1: 最短路径为:5，依次经过：4-3-2-1

4 - 2: 最短路径为:3，依次经过：4-3-2

4 - 3: 最短路径为:2，依次经过：4-3