All-Pairs Shortest Paths (Floyd-Warshall Algorithm): หาระยะทางสั้นที่สุดทุกคู่

All-Pairs Shortest Path (Floyd-Warshall Algorithm) หาระยะทางสั้นที่สุดระหว่างทุกคู่โหนดจาก Weighted Graph ผลลัพธ์เป็น Matrix แสดงระยะทางขั้นต่ำจากโหนดใดโหนดหนึ่งไปยังโหนดอื่นๆ ทั้งหมด

เริ่มต้น Output Matrix เหมือน Cost Matrix ของกราฟ แล้วอัปเดต Matrix ด้วยโหนด k ทุกตัวเป็น Intermediate Vertex

Time Complexity: O(V³) โดย V = จำนวนโหนด

Input

Cost Matrix ของกราฟ

0 3 6 ∞ ∞ ∞ ∞
3 0 2 1 ∞ ∞ ∞
6 2 0 1 4 2 ∞
∞ 1 1 0 2 ∞ 4
∞ ∞ 4 2 0 2 1
∞ ∞ 2 ∞ 2 0 1
∞ ∞ ∞ 4 1 1 0

Output

Matrix of All-Pairs Shortest Path

0 3 4 5 6 7 7
3 0 2 1 3 4 4
4 2 0 1 3 2 3
5 1 1 0 2 3 3
6 3 3 2 0 2 1
7 4 2 3 2 0 1
7 4 3 3 1 1 0

Algorithm

floydWarshal(cost)

Input: Cost Matrix ของกราฟ
Output: Matrix ระยะทางสั้นที่สุดระหว่างโหนดใดโหนดหนึ่ง

Begin
    for k := 0 to n do
        for i := 0 to n do
            for j := 0 to n do
                if cost[i,k] + cost[k,j] < cost[i,j] then
                    cost[i,j] := cost[i,k] + cost[k,j]
                done
            done
        done
    display current cost matrix
End

ตัวอย่างโค้ด (C++)

#include <iostream>
#include <iomanip>
#define NODE 7
#define INF 999
using namespace std;

int costMat[NODE][NODE] = {
    {0, 3, 6, INF, INF, INF, INF},
    {3, 0, 2, 1, INF, INF, INF},
    {6, 2, 0, 1, 4, 2, INF},
    {INF, 1, 1, 0, 2, INF, 4},
    {INF, INF, 4, 2, 0, 2, 1},
    {INF, INF, 2, INF, 2, 0, 1},
    {INF, INF, INF, 4, 1, 1, 0}
};

void floydWarshal() {
    int cost[NODE][NODE];
    for(int i = 0; i < NODE; i++)
        for(int j = 0; j < NODE; j++)
            cost[i][j] = costMat[i][j];
    for(int k = 0; k < NODE; k++)
        for(int i = 0; i < NODE; i++)
            for(int j = 0; j < NODE; j++)
                if(cost[i][k] + cost[k][j] < cost[i][j])
                    cost[i][j] = cost[i][k] + cost[k][j];
    cout << "The matrix:" << endl;
    for(int i = 0; i < NODE; i++) {
        for(int j = 0; j < NODE; j++)
            cout << setw(3) << cost[i][j];
        cout << endl;
    }
}

int main() {
    floydWarshal();
}

Output

The matrix:
0 3 5 4 6 7 7
3 0 2 1 3 4 4
5 2 0 1 3 2 3
4 1 1 0 2 3 3
6 3 3 2 0 2 1
7 4 2 3 2 0 1
7 4 3 3 1 1 0