Floyd-Warshall演算法

習題預習

1. 在無向圖中，如何找出從給定源節點到所有其他節點的最短路徑？
2. 在有向圖中，如何找出所有節點彼此之間的最短路徑？
3. 在有向圖中，如何找出所有節點彼此之間的最長路徑？
4. 在一個網格圖中，如何找出所有格子之間的最短路徑？
5. 在一個帶權重的有向圖中，如何找出從某個葉子節點到根節點的最短路徑？

說明知識

Floyd-Warshall Algorithm（弗洛伊德-沃捨爾算法）是解決圖中所有節點之間最短路徑的經典算法之一，它是一種動態規划算法，以及解決所有點對之間最短路徑的做法，同時也適用於帶有負邊權的圖。

算法的基本思想是維護一個二維數組D，用來記錄任意兩點之間的最短路徑長度。初始時，D[i][j]表示從節點i到節點j的距離，如果i和j不直接相鄰，那麼D[i][j]=正無窮。算法每進行一輪迭代，便會將D[i][j]和D[i][k]+D[k][j]（相當於以k作為中介）進行比較更新，最終得到任意兩點之間的最短路徑長度。

以下是弗洛伊德-沃捨爾算法的偽代碼：

1. for k from 1 to |V|
2.      for i from 1 to |V|
3.          for j from 1 to |V|
4.              if D[i][j] > D[i][k] + D[k][j] then
5.                  D[i][j] = D[i][k] + D[k][j]

舉例說明：
考慮下圖：

構建鄰接矩陣如下：

    1   2   3   4   5   6
  -------------------------
1 | 0   1   ∞   ∞   5   ∞
2 | ∞   0   1   ∞   ∞   ∞
3 | ∞   ∞   0   2   ∞   ∞
4 | ∞   ∞   ∞   0   ∞   1
5 | ∞   ∞   ∞   1   0   2
6 | ∞   ∞   ∞   ∞   ∞   0

其中，∞表示兩點之間沒有連通路徑。

接下來，我們可以運用Floyd-Warshall Algorithm算法來求得任意兩點之間的最短路徑長度，具體過程如下：

第一輪迭代：k=1

D[1][2]=min(∞, ∞+1)=1, 
D[1][5]=min(5, ∞+1)=6,
D[2][3]=min(∞,∞+1)=1,
D[3][4]=min(∞,∞+2)=2,
D[4][6]=min(∞,∞+1)=1,
D[5][6]=min(∞,∞+2)=2

    1   2   3   4   5   6
  -------------------------
1 | 0   1   ∞   ∞   5   ∞
2 | ∞   0   1   ∞   ∞   ∞
3 | ∞   2   0   2   ∞   ∞
4 | ∞   ∞   ∞   0   ∞   1
5 | ∞   ∞   ∞   1   0   2
6 | ∞   ∞   ∞   ∞   ∞   0

第二輪迭代：k=2

D[1][3]=min(∞,1+1)=2,
D[1][6]=min(∞,5+2)=7,
D[2][4]=min(1,1+∞)=1,
D[3][6]=min(∞,2+2)=4,
D[4][5]=min(∞,1+2)=3

    1   2   3   4   5   6
  -------------------------
1 | 0   1   2   ∞   5   7
2 | ∞   0   1   2   ∞   3
3 | ∞   2   0   2   ∞   4
4 | ∞   ∞   ∞   0   3   1
5 | ∞   ∞   ∞   1   0   2
6 | ∞   ∞   ∞   ∞   ∞   0

第三輪迭代：k=3

D[1][4]=min(∞,2+2)=4,
D[2][5]=min(∞,1+2)=3,
D[3][6]=min(2,2+2)=2,
D[4][6]=min(1,3+1)=1,
D[5][3]=min(∞,2+2)=2

    1   2   3   4   5   6
  -------------------------
1 | 0   1   2   4   5   6
2 | ∞   0   1   2   3   3
3 | ∞   2   0   2   4   2
4 | ∞   ∞   ∞   0   3   1
5 | ∞   ∞   2   1   0   2
6 | ∞   ∞   ∞   ∞   ∞   0

第四輪迭代：k=4

D[2][6]=min(3,3+1)=3,
D[3][5]=min(2,2+4)=2,
D[4][2]=min(2,3+1)=2,
D[4][6]=min(1,3+1)=1,
D[5][1]=min(∞,2+5)=7

    1   2   3   4   5   6
  -------------------------
1 | 0   1   2   4   5   6
2 | ∞   0   1   2   3   3
3 | ∞   2   0   2   4   2
4 | ∞   2   3   0   3   1
5 | 7   6   2   1   0   2
6 | ∞   ∞   ∞   ∞   ∞   0

最終的結果是：

    1   2   3   4   5   6
  -------------------------
1 | 0   1   2   4   5   6
2 | ∞   0   1   2   3   3
3 | ∞   2   0   2   4   2
4 | ∞   2   3   0   3   1
5 | 7   6   2   1   0   2
6 | ∞   ∞   ∞   ∞   ∞   0

因此，我們可以得到所有點對之間的最短距離。例如，點1到點6的最短距離為6，點2到點1的最短距離為∞，點4到點5的最短距離為3 等。

總結：Floyd-Warshall Algorithm算法對有些權值為負的圖仍然有效，並且由於操作矩陣，理論上算法時間複雜度為O(n^3)，適用於處理規模不是特別大的圖，而且不受圖形中負邊權的影響，非常適合多源最短路徑問題。

彙總重點

1. Floyd-Warshall Algorithm（F-W算法）是一種動態規划算法，用於解決全源最短路問題。
2. F-W算法利用矩陣來存儲每對節點之間的最短路長度。
3. 矩陣中每個元素的值代表從i到j的最短路長度，其中i和j是矩陣下標。
4. F-W算法每次更新矩陣中保存的最短路長度，以便找出每對節點之間的最短路。
5. F-W算法的核心思想是利用動態規劃思想，將問題分解為子問題依次求解。
6. 在F-W算法中，我們先將圖表示成一個帶權有向圖（即邊帶權），然後利用矩陣來保存最短路長度。
7. F-W算法主要包括初始化矩陣、遍歷圖、更新矩陣等步驟。
8. 儘管F-W算法的時間複雜度較高（為O(N^3)），但它可以處理帶權有向圖中任意兩點之間的最短路問題，並且效果非常穩定。

知識測驗

1. 給定一張有向帶權圖，求從任意一點到任意一點的最短路徑。如果兩點之間沒有路徑，輸出inf。

程式碼如下：
void Floyd() {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (d[i][k] != INF && d[k][j] != INF && d[i][j] > d[i][k] + d[k][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                }
            }
        }
    }
}

2. 給定一張無向帶權圖，求圖中的最小生成樹。如果圖不連通，則輸出-1。

程式碼如下：
void Floyd() {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (d[i][k] != INF && d[k][j] != INF && d[i][j] > d[i][k] + d[k][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                }
            }
        }
    }
}

3. 給定一張有向帶權圖，求從任意一點到任意一點的最短路徑，如果存在負權環，輸出-1。

程式碼如下：
int Floyd() {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (d[i][k] != INF && d[k][j] != INF && d[i][j] > d[i][k] + d[k][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                }
            }
        }
    }
    for (int k = 1; k <= n; k++) {
        if (d[k][k] < 0) { // 存在負權環
            return -1;
        }
    }
    return 0;
}

4. 給定一張有向帶權圖，求從每個點出發能到達的所有點之間的最小總權值和。

程式碼如下：
void Floyd() {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (d[i][k] != INF && d[k][j] != INF && d[i][j] > d[i][k] + d[k][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        int sum = 0;
        for (int j = 1; j <= n; j++) {
            if (d[i][j] != INF) {
                sum += d[i][j];
            }
        }
        printf("%d ", sum);
    }
}

5. 給定一張有向帶權圖，求從任意一點到任意一點經過正好k條邊的最短路徑。

程式碼如下：
void Floyd(int k) {
for (int l = 1; l <= k; l++) { // l表示經過l條邊
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int m = 1; m <= n; m++) {
if (d[i][m] != INF && d[m][j] != INF && d[i][j] > d[i][m] + d[m][j]) {
d[i][j] = d[i][m] + d[m][j];
}
}
}
}
}
}