Floyd-Warshall 算法 · Programiz 中文系列教程

# Floyd-Warshall 算法 > 原文： [https://www.programiz.com/dsa/floyd-warshall-algorithm](https://www.programiz.com/dsa/floyd-warshall-algorithm) #### 在本教程中，您將學習 floyd-warshall 算法的工作原理。此外，您還將找到 C，C++ ，Java 和 Python 中的 floyd-warshall 算法的工作示例。 Floyd-Warshall 算法是一種用于找到加權圖中所有頂點對之間的最短路徑的算法。該算法適用于有向和無向加權圖。但是，它不適用于周期為負的圖（周期中邊的總和為負）。加權圖是其中每個邊都有與之關聯的數值的圖。 Floyd-Warhshall 算法也稱為 Floyd 算法，Roy-Floyd 算法，Roy-Warshall 算法或 WFI 算法。該算法遵循[動態規劃](/dsa/dynamic-programming)方法來找到最短路徑。 * * * ## Floyd-Warshall 算法如何工作？讓給定的圖形為： ![graph](https://img.kancloud.cn/21/f6/21f683ec7faa488d4b85067e0a9b9f9f_384x344.png "initial graph") 初始圖請按照以下步驟查找所有頂點對之間的最短路徑。 1. 創建大小為`n*n`的矩陣`A^1`，其中`n`是頂點數。行和列的索引分別為`i`和`j`。`i`和`j`是圖形的頂點。每個單元格`A[i][j]`填充了從第`i`個頂點到第`j`個頂點的距離。如果沒有從第`i`個頂點到第`j`個頂點的路徑，則該單元將保留為無窮大。 ![matrix floyd warshall algorithm](https://img.kancloud.cn/96/25/9625a299a3057553bbebbe32bb6c1dca_574x428.png "matrix") 用第`i`個頂點與第`j`個頂點之間的距離填充每個單元格 2. 現在，使用矩陣`A^0`創建一個矩陣`A^1`。第一列和第一行中的元素保持原樣。其余單元格按以下方式填充。令`k`為從源到目標的最短路徑中的中間頂點。在此步驟中，`k`是第一個頂點。`A[i][j]`填充有`(A[i][k] + A[k][j]) if (A[i][j] > A[i][k] + A[k][j])`。也就是說，如果從源到目的地的直接距離大于通過頂點`k`的路徑，則單元格將填充`A[i][k] + A[k][j]`。在此步驟中，`k`為頂點 1。我們計算通過此頂點`k`從源頂點到目標頂點的距離。 ![matrix floyd warshall algorithm](https://img.kancloud.cn/29/6e/296e395022fc2b90be408b83f057be14_1086x428.png "matrix A1") 計算通過此頂點`k`從源頂點到目的頂點的距離例如：對于`A^1[2, 4]`，從頂點 2 到 4 的直接距離是 4 并且從頂點 2 到 4 到頂點（即從頂點 2 到 1 和從頂點 1 到 4）的距離之和為 7。由于`4 < 7`，`A^0[2, 4]`用 4 填充。 3. 類似地，使用`A^3`創建`A^2`。第二列和第二行中的元素保持原樣。在此步驟中，`k`是第二個頂點（即頂點 2）。其余步驟與**步驟 2** 中的步驟相同。 ![matrix floyd warshall algorithm](https://img.kancloud.cn/65/7a/657ab568a0f3c071e56eba757d28800f_1086x428.png "matrix A2") 計算通過此頂點 2 從源頂點到目標頂點的距離 4. 同樣，還創建了`A^3`和`A^4`。 ![matrix floyd warshall algorithm](https://img.kancloud.cn/6a/9e/6a9ea6565403e3e20f9846713f9b4950_1086x428.png "matrix A3") 計算通過此頂點從源頂點到目標頂點的距離。 ![matrix floyd warshall algorithm](https://img.kancloud.cn/a6/02/a60284732391e9bb40c5f6a0cf8ddc31_1086x428.png "matrix A4") 計算通過定點 4 從源頂點到目標頂點的距離。 5. `A^4`給出每對頂點之間的最短路徑。 * * * ## 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++ 示例 ```py # 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) ``` ```java // 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); } } ``` ```c // 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); } ``` ```cpp // 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(n^3)`。 ### 空間復雜度 Floyd-Warshall 算法的空間復雜度為`O(n^2)`。 * * * ## Floyd Warshall 算法應用 * 找到有向圖的最短路徑 * 查找有向圖的傳遞閉包 * 查找實矩陣的逆 * 測試無向圖是否是二分圖