上查看所有课程
Floyd-Warshall算法是一种用于寻找加权图中所有顶点对之间最短路径的算法。该算法适用于有向和无向加权图。但是，它不适用于具有负权环（边权重之和为负）的图。
加权图是一种每条边都有一个数值与之关联的图。
Floyd-Warhshall算法也称为Floyd算法、Roy-Floyd算法、Roy-Warshall算法或WFI算法。
该算法遵循动态规划方法来查找最短路径。
Floyd-Warshall算法如何工作？
设给定的图为
按照以下步骤查找所有顶点对之间的最短路径。
- 创建一个维度为
n*n的矩阵A0，其中n是顶点的数量。行和列分别由i和j索引。 i和j是图的顶点。
每个单元格A[i][j]都填充了从第i个顶点到第j个顶点的距离。如果从第i个顶点到第j个顶点没有路径，则该单元格留为空（无穷大）。
用顶点i和j之间的距离填充每个单元格 - 现在，使用矩阵
A0创建一个矩阵A1。第一列和第一行的元素保持不变。其余单元格按如下方式填充。
设k为从源到目的地的最短路径上的中间顶点。在此步骤中，k是第一个顶点。如果A[i][j] > A[i][k] + A[k][j]，则A[i][j]被填充为(A[i][k] + A[k][j])。
也就是说，如果源到目的地的直接距离大于通过顶点k的路径，则该单元格将被填充为A[i][k] + A[k][j]。
在此步骤中，k为顶点1。我们通过此顶点k计算从源顶点到目的地顶点的距离。
计算从源顶点到目的地顶点通过此顶点k的距离
例如：对于A1[2, 4]，顶点2到4的直接距离是4，而从顶点2到1再到顶点1到4的距离之和是7。由于4 < 7，所以A0[2, 4]被填充为4。 - 同样，使用
A1创建A2。第二列和第二行的元素保持不变。
在此步骤中，k是第二个顶点（即顶点2）。其余步骤与**步骤2**中的相同。
计算从源顶点到目的地顶点通过此顶点2的距离 - 同样，也创建了
A3和A4。
计算从源顶点到目的地顶点通过此顶点3的距离 
计算从源顶点到目的地顶点通过此顶点4的距离 A4给出了每对顶点之间的最短路径。
Floyd-Warshall 算法
n = no of vertices
A = matrix of dimension n*n
for k = 1 to n
for i = 1 to n
for j = 1 to n
Ak[i, j] = min (Ak-1[i, j], Ak-1[i, k] + Ak-1[k, j])
return A
Python、Java 和 C/C++ 示例
# Floyd Warshall Algorithm in python
# The number of vertices
nV = 4
INF = 999
# Algorithm implementation
def floyd_warshall(G):
distance = list(map(lambda i: list(map(lambda j: j, i)), G))
# Adding vertices individually
for k in range(nV):
for i in range(nV):
for j in range(nV):
distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
print_solution(distance)
# Printing the solution
def print_solution(distance):
for i in range(nV):
for j in range(nV):
if(distance[i][j] == INF):
print("INF", end=" ")
else:
print(distance[i][j], end=" ")
print(" ")
G = [[0, 3, INF, 5],
[2, 0, INF, 4],
[INF, 1, 0, INF],
[INF, INF, 2, 0]]
floyd_warshall(G)// Floyd Warshall Algorithm in Java
class FloydWarshall {
final static int INF = 9999, nV = 4;
// Implementing floyd warshall algorithm
void floydWarshall(int graph[][]) {
int matrix[][] = new int[nV][nV];
int i, j, k;
for (i = 0; i < nV; i++)
for (j = 0; j < nV; j++)
matrix[i][j] = graph[i][j];
// Adding vertices individually
for (k = 0; k < nV; k++) {
for (i = 0; i < nV; i++) {
for (j = 0; j < nV; j++) {
if (matrix[i][k] + matrix[k][j] < matrix[i][j])
matrix[i][j] = matrix[i][k] + matrix[k][j];
}
}
}
printMatrix(matrix);
}
void printMatrix(int matrix[][]) {
for (int i = 0; i < nV; ++i) {
for (int j = 0; j < nV; ++j) {
if (matrix[i][j] == INF)
System.out.print("INF ");
else
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
int graph[][] = { { 0, 3, INF, 5 }, { 2, 0, INF, 4 }, { INF, 1, 0, INF }, { INF, INF, 2, 0 } };
FloydWarshall a = new FloydWarshall();
a.floydWarshall(graph);
}
}// Floyd-Warshall Algorithm in C
#include <stdio.h>
// defining the number of vertices
#define nV 4
#define INF 999
void printMatrix(int matrix[][nV]);
// Implementing floyd warshall algorithm
void floydWarshall(int graph[][nV]) {
int matrix[nV][nV], i, j, k;
for (i = 0; i < nV; i++)
for (j = 0; j < nV; j++)
matrix[i][j] = graph[i][j];
// Adding vertices individually
for (k = 0; k < nV; k++) {
for (i = 0; i < nV; i++) {
for (j = 0; j < nV; j++) {
if (matrix[i][k] + matrix[k][j] < matrix[i][j])
matrix[i][j] = matrix[i][k] + matrix[k][j];
}
}
}
printMatrix(matrix);
}
void printMatrix(int matrix[][nV]) {
for (int i = 0; i < nV; i++) {
for (int j = 0; j < nV; j++) {
if (matrix[i][j] == INF)
printf("%4s", "INF");
else
printf("%4d", matrix[i][j]);
}
printf("\n");
}
}
int main() {
int graph[nV][nV] = {{0, 3, INF, 5},
{2, 0, INF, 4},
{INF, 1, 0, INF},
{INF, INF, 2, 0}};
floydWarshall(graph);
}// Floyd-Warshall Algorithm in C++
#include <iostream>
using namespace std;
// defining the number of vertices
#define nV 4
#define INF 999
void printMatrix(int matrix[][nV]);
// Implementing floyd warshall algorithm
void floydWarshall(int graph[][nV]) {
int matrix[nV][nV], i, j, k;
for (i = 0; i < nV; i++)
for (j = 0; j < nV; j++)
matrix[i][j] = graph[i][j];
// Adding vertices individually
for (k = 0; k < nV; k++) {
for (i = 0; i < nV; i++) {
for (j = 0; j < nV; j++) {
if (matrix[i][k] + matrix[k][j] < matrix[i][j])
matrix[i][j] = matrix[i][k] + matrix[k][j];
}
}
}
printMatrix(matrix);
}
void printMatrix(int matrix[][nV]) {
for (int i = 0; i < nV; i++) {
for (int j = 0; j < nV; j++) {
if (matrix[i][j] == INF)
printf("%4s", "INF");
else
printf("%4d", matrix[i][j]);
}
printf("\n");
}
}
int main() {
int graph[nV][nV] = {{0, 3, INF, 5},
{2, 0, INF, 4},
{INF, 1, 0, INF},
{INF, INF, 2, 0}};
floydWarshall(graph);
}Floyd Warshall算法复杂度
时间复杂度
有三个循环。每个循环都有常数复杂度。因此，Floyd-Warshall算法的时间复杂度为O(n3)。
空间复杂度
Floyd-Warshall算法的空间复杂度为O(n2)。
Floyd Warshall算法的应用
- 用于查找有向图中的最短路径
- 用于查找有向图的传递闭包
- 用于查找实数矩阵的逆
- 用于测试无向图是否为二分图
