菊爽开塞露专卖旗舰店
弗洛伊德算法能够在指定图结构中找到各个顶点之间的最短路径，该算法既适用于无向加权图，也适用于有向加权图。
注意，弗洛伊德算法仅允许非环路的路径权值为负数。换句话说，如果图中某个环路的路径权值为负数，该算法将无法正常执行。
弗洛伊德算法的工作原理
弗洛伊德算法是基于动态规划思想实现的，我们以图 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#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
