Floyd-Warshall Algorithm: หา Shortest Path ทุกคู่ในกราฟ

Floyd-Warshall Algorithm ใช้หา All-Pairs Shortest Path ในกราฟที่มีน้ำหนัก (weighted graph) ผลลัพธ์คือเมทริกซ์ที่แสดงระยะทางสั้นที่สุดระหว่างทุกคู่ของโหนด

ตัวอย่าง Input และ Output

Input: Cost Matrix (7 โหนด, INF = ไม่มีขอบ)
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

Output: All-Pairs Shortest Path Matrix
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

อัลกอริทึม Floyd-Warshall

ฟังก์ชัน floydWarshal(cost)

แนวคิดหลัก:

พิจารณาโหนด k เป็น โหนดกลาง (intermediate vertex) ทีละตัว อัปเดตระยะทางระหว่างทุกคู่ (i, j) หากการผ่าน k ให้ระยะทางสั้นกว่า

ขั้นตอน:

1. คัดลอก cost matrix ไปยังเมทริกซ์ cost ใหม่
2. for k = 0 ถึง n-1 (โหนดกลาง):
   • for i = 0 ถึง n-1 (ต้นทาง):
     • for j = 0 ถึง n-1 (ปลายทาง):
       • ถ้า cost[i][k] + cost[k][j] < cost[i][j]
       • → cost[i][j] = cost[i][k] + cost[k][j]
3. เมทริกซ์ cost ตอนจบคือคำตอบ

ตัวอย่างโค้ด 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();
    return 0;
}

Output

The matrix:
  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

ความซับซ้อน

• Time: O(V³) - ลูป 3 ชั้น V × V × V
• Space: O(V²) - เมทริกซ์ระยะทาง

การประยุกต์ใช้

• หา Transitive Closure (การเข้าถึงได้หรือไม่)
• ตรวจจับ Negative Cycle (ถ้า cost[i][i] < 0)
• คำนวณระยะทางสั้นที่สุดในเครือข่ายขนาดเล็ก-ปานกลาง