弗洛伊德-沃歇爾演算法

Table of content
上一頁
下一頁

弗洛伊德-沃歇爾演算法是一種圖演算法，用於查詢加權圖中所有頂點之間的最短路徑。該演算法不同於其他最短路徑演算法；簡單來說，該演算法使用圖中的每個頂點作為樞紐，檢查它是否提供了從一點到另一點的最快路徑。

弗洛伊德-沃歇爾演算法適用於有向和無向加權圖，除非這些圖不包含任何負環。負環是指圖中所有邊的總和不能導致負數。

由於該演算法處理重疊子問題——由頂點作為樞紐找到的路徑被儲存以解決後續步驟——因此它使用動態規劃方法。

弗洛伊德-沃歇爾演算法是所有對最短路徑演算法中的一種方法，它使用圖的鄰接矩陣表示來求解。

Floyd-Warshall演算法

考慮一個圖，G = {V, E}，其中V是圖中所有頂點的集合，E是圖中所有邊的集合。圖G以鄰接矩陣A的形式表示，該矩陣包含連線兩個頂點的每條邊的所有權重。

演算法

步驟1 - 構造一個鄰接矩陣A，其中包含圖中所有邊的權重。如果兩個頂點之間沒有路徑，則將值標記為∞。

步驟2 - 從A派生另一個鄰接矩陣A1，在A1中保持原始鄰接矩陣的第1行和第1列不變。對於其餘的值，例如A1[i,j]，如果A[i,j]>A[i,k]+A[k,j]，則用A[i,k]+A[k,j]替換A1[i,j]。否則，不要更改值。在此步驟中，k = 1（第一個頂點作為樞紐）。

步驟3 - 透過為每個樞紐頂點更改k值，對圖中的所有頂點重複步驟2，直到獲得最終矩陣。

步驟4 - 獲得的最終鄰接矩陣是包含所有最短路徑的最終解。

虛擬碼

Floyd-Warshall(w, n){ // w: weights, n: number of vertices
   for i = 1 to n do // initialize, D (0) = [wij]
      for j = 1 to n do{
         d[i, j] = w[i, j];
      }
      for k = 1 to n do // Compute D (k) from D (k-1)
         for i = 1 to n do
            for j = 1 to n do
               if (d[i, k] + d[k, j] < d[i, j]){
                  d[i, j] = d[i, k] + d[k, j];
               }
      return d[1..n, 1..n];
}

示例

考慮以下有向加權圖G = {V, E}。使用弗洛伊德-沃歇爾演算法查詢圖中所有頂點之間的最短路徑。

directed_weighted_graph

解答

步驟1

構造一個鄰接矩陣A，其中所有距離作為值。

$$A=\begin{matrix} 0 & 5& \infty & 6& \infty \\ \infty & 0& 1& \infty& 7\\ 3 & \infty& 0& 4& \infty\\ \infty & \infty& 2& 0& 3\\ 2& \infty& \infty& 5& 0\\ \end{matrix}$$

步驟2

將上述鄰接矩陣作為輸入，透過僅保持第一行和第一列不變來派生另一個矩陣A0。取k = 1，並用A[i,k]+A[k,j]替換所有其他值。

$$A=\begin{matrix} 0 & 5& \infty & 6& \infty \\ \infty & & & & \\ 3& & & & \\ \infty& & & & \\ 2& & & & \\ \end{matrix}$$

$$A_{1}=\begin{matrix} 0 & 5& \infty & 6& \infty \\ \infty & 0& 1& \infty& 7\\ 3 & 8& 0& 4& \infty\\ \infty & \infty& 2& 0& 3\\ 2& 7& \infty& 5& 0\\ \end{matrix}$$

步驟3

將上述鄰接矩陣作為輸入，透過僅保持第一行和第一列不變來派生另一個矩陣A0。取k = 1，並用A[i,k]+A[k,j]替換所有其他值。

$$A_{2}=\begin{matrix} & 5& & & \\ \infty & 0& 1& \infty& 7\\ & 8& & & \\ & \infty& & & \\ & 7& & & \\ \end{matrix}$$

$$A_{2}=\begin{matrix} 0 & 5& 6& 6& 12 \\ \infty & 0& 1& \infty& 7\\ 3 & 8& 0& 4& 15\\ \infty & \infty& 2& 0& 3\\ 2 & 7& 8& 5& 0 \\ \end{matrix}$$

步驟4

將上述鄰接矩陣作為輸入，透過僅保持第一行和第一列不變來派生另一個矩陣A0。取k = 1，並用A[i,k]+A[k,j]替換所有其他值。

$$A_{3}=\begin{matrix} & & 6& & \\ & & 1& & \\ 3 & 8& 0& 4& 15\\ & & 2& & \\ & & 8& & \\ \end{matrix}$$

$$A_{3}=\begin{matrix} 0 & 5& 6& 6& 12 \\ 4 & 0& 1& 5& 7\\ 3 & 8& 0& 4& 15\\ 5 & 10& 2& 0& 3\\ 2 & 7& 8& 5& 0 \\ \end{matrix}$$

步驟5

將上述鄰接矩陣作為輸入，透過僅保持第一行和第一列不變來派生另一個矩陣A0。取k = 1，並用A[i,k]+A[k,j]替換所有其他值。

$$A_{4}=\begin{matrix} & & & 6& \\ & & & 5& \\ & & & 4& \\ 5 & 10& 2& 0& 3\\ & & & 5& \\ \end{matrix}$$

$$A_{4}=\begin{matrix} 0 & 5& 6& 6& 9 \\ 4 & 0& 1& 5& 7\\ 3 & 8& 0& 4& 7\\ 5 & 10& 2& 0& 3\\ 2 & 7& 7& 5& 0 \\ \end{matrix}$$

步驟6

將上述鄰接矩陣作為輸入，透過僅保持第一行和第一列不變來派生另一個矩陣A0。取k = 1，並用A[i,k]+A[k,j]替換所有其他值。

$$A_{5}=\begin{matrix} & & & & 9 \\ & & & & 7\\ & & & & 7\\ & & & & 3\\ 2 & 7& 7& 5& 0 \\ \end{matrix}$$

$$A_{5}=\begin{matrix} 0 & 5& 6& 6& 9 \\ 4 & 0& 1& 5& 7\\ 3 & 8& 0& 4& 7\\ 5 & 10& 2& 0& 3\\ 2 & 7& 7& 5& 0 \\ \end{matrix}$$

分析

從上面的虛擬碼可以看出，弗洛伊德-沃歇爾演算法使用三個for迴圈來查詢圖中所有頂點對之間的最短距離。因此，弗洛伊德-沃歇爾演算法的時間複雜度為O(n3)，其中'n'是圖中頂點的數量。該演算法的空間複雜度為O(n2)。

實現

以下是使用成本鄰接矩陣查詢圖中最短路徑的弗洛伊德-沃歇爾演算法的實現 -

C C++ Java Python
#include <stdio.h>
void floyds(int b[3][3]) {
   int i, j, k;
   for (k = 0; k < 3; k++) {
      for (i = 0; i < 3; i++) {
         for (j = 0; j < 3; j++) {
            if ((b[i][k] * b[k][j] != 0) && (i != j)) {
               if ((b[i][k] + b[k][j] < b[i][j]) || (b[i][j] == 0)) {
                  b[i][j] = b[i][k] + b[k][j];
               }
            }
         }
      }
   }
   for (i = 0; i < 3; i++) {
      printf("Minimum Cost With Respect to Node: %d\n", i);
      for (j = 0; j < 3; j++) {
         printf("%d\t", b[i][j]);
      }
   }
}

int main() {
   int b[3][3] = {0};
   b[0][1] = 10;
   b[1][2] = 15;
   b[2][0] = 12;
   floyds(b);
   return 0;
}

輸出

Minimum Cost With Respect to Node: 0
0	10	25	
Minimum Cost With Respect to Node: 1
27	0	15	
Minimum Cost With Respect to Node: 2
12	22	0	

#include <iostream>
using namespace std;
void floyds(int b[][3]){
   int i, j, k;
   for (k = 0; k < 3; k++) {
      for (i = 0; i < 3; i++) {
         for (j = 0; j < 3; j++) {
            if ((b[i][k] * b[k][j] != 0) && (i != j)) {
               if ((b[i][k] + b[k][j] < b[i][j]) || (b[i][j] == 0)) {
                  b[i][j] = b[i][k] + b[k][j];
               }
            }
         }
      }
   }
   for (i = 0; i < 3; i++) {
      cout<<"Minimum Cost With Respect to Node:"<<i<<endl;
      for (j = 0; j < 3; j++) {
         cout<<b[i][j]<<"\t";
      }
   }
}
int main(){
   int b[3][3];
   for (int i = 0; i < 3; i++) {
      for (int j = 0; j < 3; j++) {
         b[i][j] = 0;
      }
   }
   b[0][1] = 10;
   b[1][2] = 15;
   b[2][0] = 12;
   floyds(b);
   return 0;
}

輸出

Minimum Cost With Respect to Node:0
0  10  25	
Minimum Cost With Respect to Node:1
27  0  15	
Minimum Cost With Respect to Node:2
12  22  0

import java.util.Arrays;
public class Main {
   public static void floyds(int[][] b) {
      int i, j, k;
      for (k = 0; k < 3; k++) {
         for (i = 0; i < 3; i++) {
            for (j = 0; j < 3; j++) {
               if ((b[i][k] * b[k][j] != 0) && (i != j)) {
                  if ((b[i][k] + b[k][j] < b[i][j]) || (b[i][j] == 0)) {
                     b[i][j] = b[i][k] + b[k][j];
                  }
               }
            }
         }
      }
      for (i = 0; i < 3; i++) {
         System.out.println("Minimum Cost With Respect to Node:" + i);
         for (j = 0; j < 3; j++) {
            System.out.print(b[i][j] + "\t");
         }
      }
   }
   public static void main(String[] args) {
      int[][] b = new int[3][3];
      for (int i = 0; i < 3; i++) {
         Arrays.fill(b[i], 0);
      }
      b[0][1] = 10;
      b[1][2] = 15;
      b[2][0] = 12;
      floyds(b);
   }
}

輸出

Minimum Cost With Respect to Node:0
0  10  25	
Minimum Cost With Respect to Node:1
27  0  15	
Minimum Cost With Respect to Node:2
12  22  0		

import numpy as np
def floyds(b):
    for k in range(3):
        for i in range(3):
            for j in range(3):
                if (b[i][k] * b[k][j] != 0) and (i != j):
                    if (b[i][k] + b[k][j] < b[i][j]) or (b[i][j] == 0):
                        b[i][j] = b[i][k] + b[k][j]
    for i in range(3):
        print("Minimum Cost With Respect to Node:", i)
        for j in range(3):
            print(b[i][j], end="\t")
b = np.zeros((3, 3), dtype=int)
b[0][1] = 10
b[1][2] = 15
b[2][0] = 12
#calling the method
floyds(b)

輸出

Minimum Cost With Respect to Node: 0
0	10	25	
Minimum Cost With Respect to Node: 1
27	0	15	
Minimum Cost With Respect to Node: 2
12	22	0
列印頁面
上一頁
下一頁
廣告