弗洛伊德算法能够在指定图结构中找到各个顶点之间的最短路径,该算法既适用于无向加权图,也适用于有向加权图。
注意,弗洛伊德算法仅允许非环路的路径权值为负数。换句话说,如果图中某个环路的路径权值为负数,该算法将无法正常执行。
弗洛伊德算法的工作原理
弗洛伊德算法是基于动态规划思想实现的,我们以图 1 所示的有向加权图为例,给您演示该算法的工作原理。
图 1 有向加权图
1) 建立一张表格(如表 1 所示),记录图结构中各个路径的权值信息:
顶点 | 1 | 2 | 3 | 4 |
---|---|---|---|---|
1 | 0 | 3 | ∞ | 5 |
2 | 2 | 0 | ∞ | 4 |
3 | ∞ | 1 | 0 | ∞ |
4 | ∞ | ∞ | 2 | 0 |
2) 将顶点 1 作为其它顶点之间最短路径必须经过的顶点,依次判断是否比表 1 中记录的路径值更小,如果更小,则表明顶点之间存在更短的路径,更新表 1 中的路径数据。
也就是说,依次判断以下这些路径的权值是否比表 1 记录的权值更小:
2-1-3 权值为 2 + ∞ = ∞,表 1 中记录的 2-3 的路径值也是 ∞,因此不更新;
2-1-4 权值为 2 + 5 = 7,表 1 中记录的 2-4 的路径值为 4, 7 > 4,因此不更新;
3-1-2 权值为 ∞ + 3,不更新;
3-1-4 权值为 ∞ + 5,不更新;
4-1-2 权值为 ∞ + 3,不更新;
4-1-3 权值为 ∞ + ∞,不更新。
由此断定,以顶点 1 作为中间顶点,并不能使其它各顶点之间路径的权值更小。
3) 将顶点 2 作为其它顶点之间最短路径必须经过的顶点,依次判断是否比表 1 中记录的路径值更小:
1-2-3 权值为 3 + ∞,不更新;
1-2-4 权值为 3 + 4 = 7,表 1 中 1-4 的权值为 5,7 > 5,不更新;
3-2-1 权值为 1 + 2 = 3,表 1 中 3-1 的权值为 ∞,前者更短;
3-2-4 权值为 1 + 4 = 5,表 1 中 3-4 的权值为 ∞,前者更短;
4-2-1 权值为 ∞ + 2,不更新;
4-2-3 权值为 ∞ + ∞,不更新。
因此,我们找到了比 3-1、3-4 更短的路径,下表对表 1 进行了更新:
顶点 | 1 | 2 | 3 | 4 |
---|---|---|---|---|
1 | 0 | 3 | ∞ | 5 |
2 | 2 | 0 | ∞ | 4 |
3 | 3(3-2-1) | 1 | 0 | 5(3-2-4) |
4 | ∞ | ∞ | 2 | 0 |
4) 将顶点 3 作为其它顶点之间最短路径必须经过的顶点,依次判断是否比表 2 中记录的路径值更小:
1-3-2 权值为 ∞ + 1,不更新;
1-3-4 权值为 ∞ + 5,不更新;
2-3-1 权值为 ∞ + 3,不更新;
2-3-4 权值为 ∞ + 5,不更新;
4-3-1 权值为 2 + 3 = 5,表 2 中 4-1 的权值为 ∞,前者更短;
4-3-2 权值为 2 + 1 = 3,表 2 中 4-2 的权值为 ∞,前者更短;
因此,我们找到了比 4-1 和 4-2 更短的路径,下表对表 2 进行了更新:
顶点 | 1 | 2 | 3 | 4 |
---|---|---|---|---|
1 | 0 | 3 | ∞ | 5 |
2 | 2 | 0 | ∞ | 4 |
3 | 3(3-2-1) | 1 | 0 | 5(3-2-4) |
4 | 5(4-3-2-1) | 3(4-3-2) | 2 | 0 |
5) 将顶点 4 作为其它顶点之间最短路径必须经过的顶点,依次判断是否比表 3 中记录的路径值更小:
1-4-2 权值为 5 + 3 = 8,表 3 中 1-2 的权值为 3,不更新;
1-4-3 权值为 5 + 2 = 7,表 3 中 1-3 的权值为 ∞,前者更短;
2-4-1 权值为 4 + 5 = 9,表 3 中 2-1 的权值为 2,不更新;
2-4-3 权值为 4 + 2 = 6,表 3 中 2-3 的权值为 ∞,前者更短;
3-4-1 权值为 4 + 5 = 9,表 3 中 3-1 的权值为 3,不更新;
3-4-2 权值为 5 + 5 = 10 ,表 3 中 3-2 的权值为 1,不更新。
因此,我们找到了比 1-3 和 2-3 更短的路径,下表对表 3 进行了更新:
顶点 | 1 | 2 | 3 | 4 |
---|---|---|---|---|
1 | 0 | 3 | 7(1-4-3) | 5 |
2 | 2 | 0 | 6(2-4-3) | 4 |
3 | 3(3-2-1) | 1 | 0 | 5(3-2-4) |
4 | 5(4-3-2-1) | 3(4-3-2) | 2 | 0 |
表 4 中记录的就是各个顶点之间的最短路径。
弗洛伊德算法的具体实现
如下的 C 语言程序实现了用弗洛伊德算法查找图 1 中所有顶点之间的最短路径:
#include <stdio.h> #define V 4 //设定图中的顶点数 #define INF 65535 // 设置一个最大值 int P[V][V] = { 0 }; //记录各个顶点之间的最短路径 void printMatrix(int matrix[][V]); //输出各个顶点之间的最短路径 void printPath(int i, int j); // 递归输出各个顶点之间最短路径的具体线路 void floydWarshall(int graph[][V]); // 实现弗洛伊德算法 int main() { // 有向加权图中各个顶点之间的路径信息 int graph[V][V] = { {0, 3, INF, 5}, {2, 0, INF, 4}, {INF, 1, 0, INF}, {INF, INF, 2, 0} }; floydWarshall(graph); } // 中序递归输出各个顶点之间最短路径的具体线路 void printPath(int i, int j) { int k = P[i][j]; if (k == 0) return; printPath(i, k); printf("%d-", k + 1); printPath(k, j); } // 输出各个顶点之间的最短路径 void printMatrix(int graph[][V]) { int i, j; for (i = 0; i < V; i++) { for (j = 0; j < V; j++) { if (j == i) { continue; } printf("%d - %d: 最短路径为:", i + 1, j + 1); if (graph[i][j] == INF) printf("%s\n", "INF"); else { printf("%d", graph[i][j]); printf(",依次经过:%d-", i + 1); //调用递归函数 printPath(i, j); printf("%d\n", j + 1); } } } } // 实现弗洛伊德算法,graph[][V] 为有向加权图 void floydWarshall(int graph[][V]) { int i, j, k; //遍历每个顶点,将其作为其它顶点之间的中间顶点,更新 graph 数组 for (k = 0; k < V; k++) { for (i = 0; i < V; i++) { for (j = 0; j < V; j++) { //如果新的路径比之前记录的更短,则更新 graph 数组 if (graph[i][k] + graph[k][j] < graph[i][j]) { graph[i][j] = graph[i][k] + graph[k][j]; //记录此路径 P[i][j] = k; } } } } // 输出各个顶点之间的最短路径 printMatrix(graph); }
如下的 Java 程序实现了用弗洛伊德算法查找图 1 中所有顶点之间的最短路径:
public class Floyd { static int V = 4; // 顶点的个数 static int[][] P = new int[V][V]; // 记录各个顶点之间的最短路径 static int INF = 65535; // 设置一个最大值 // 中序递归输出各个顶点之间最短路径的具体线路 public static void printPath(int i, int j) { int k = P[i][j]; if (k == 0) return; printPath(i, k); System.out.print((k + 1) + "-"); printPath(k, j); } // 输出各个顶点之间的最短路径 public static void printMatrix(int[][] graph) { for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { if (j == i) { continue; } System.out.print((i + 1) + " - " + (j + 1) + ":最短路径为:"); if (graph[i][j] == INF) System.out.println("INF"); else { System.out.print(graph[i][j]); System.out.print(",依次经过:" + (i + 1) + "-"); // 调用递归函数 printPath(i, j); System.out.println((j + 1)); } } } } // 实现弗洛伊德算法,graph[][V] 为有向加权图 public static void floydWarshall(int[][] graph) { int i, j, k; // 遍历每个顶点,将其作为其它顶点之间的中间顶点,更新 graph 数组 for (k = 0; k < V; k++) { for (i = 0; i < V; i++) { for (j = 0; j < V; j++) { // 如果新的路径比之前记录的更短,则更新 graph 数组 if (graph[i][k] + graph[k][j] < graph[i][j]) { graph[i][j] = graph[i][k] + graph[k][j]; // 记录此路径 P[i][j] = k; } } } } // 输出各个顶点之间的最短路径 printMatrix(graph); } public static void main(String[] args) { // 有向加权图中各个顶点之间的路径信息 int[][] graph = new int[][] { { 0, 3, INF, 5 }, { 2, 0, INF, 4 }, { INF, 1, 0, INF }, { INF, INF, 2, 0 } }; floydWarshall(graph); } }
如下的 Python 程序实现了用弗洛伊德算法查找图 1 中所有顶点之间的最短路径:
V = 4 # 顶点的个数 INF = 65535 # 设定一个最大值 P = [[0]*V for i in range(V)] # 记录各个顶点之间的最短路径 # 有向加权图中各个顶点之间的路径信息 graph = [[0, 3, INF, 5], [2, 0, INF, 4], [INF, 1, 0, INF], [INF, INF, 2, 0]] # 中序递归输出各个顶点之间最短路径的具体线路 def printPath(i,j): k = P[i][j] if k == 0: return; printPath(i , k) print("%d-" % (k + 1) , end='') printPath(k , j) # 输出各个顶点之间的最短路径 def printMatrix(graph): for i in range(V): for j in range(V): if j == i: continue print("%d - %d: 最短路径为:"%(i + 1, j + 1) , end='') if graph[i][j] == INF: print("INF") else: print(graph[i][j] , end='') print(",依次经过:%d-"%(i+1) , end='') # 调用递归函数 printPath(i , j) print(j + 1) # 实现弗洛伊德算法,graph[][V] 为有向加权图 def floydWarshall(graph): # 遍历每个顶点,将其作为其它顶点之间的中间顶点,更新 graph 数组 for k in range(V): for i in range(V): for j in range(V): # 如果新的路径比之前记录的更短,则更新 graph 数组 if graph[i][k] + graph[k][j] < graph[i][j]: graph[i][j] = graph[i][k] + graph[k][j] # 记录此路径 P[i][j] = k # 输出各个顶点之间的最短路径 printMatrix(graph) 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