28.5 Floyd-Warshall และการเลือกวิธี

ทุกวิธีที่ผ่านมาหาระยะจากจุดเริ่มจุดเดียว บางโจทย์ต้องรู้ระยะของ ทุกคู่ เช่น มีคำถามเป็นแสนข้อ แต่ละข้อถามระยะระหว่างสองเมืองใดๆ หรือต้องเลือกเมืองจัดงานที่ทุกคนเดินทางมารวมกันใกล้ที่สุด ถ้ากราฟเล็ก มีวิธีที่สั้นมากเพียงลูปซ้อนสามชั้นชื่อ Floyd-Warshall หน้านี้เขียนวิธีนั้น ดูว่าลำดับของลูปสำคัญแค่ไหน แล้วปิดบทด้วยตารางเลือกวิธีตามขอบเขตของโจทย์

ความคิด

ให้ d[i][j] เป็นตารางระยะ เริ่มจาก 0 บนเส้นทแยง ระยะของถนนตรงถ้ามี และอนันต์ถ้าไม่มี แล้วค่อยๆ อนุญาตให้ใช้จุดเป็น จุดแวะกลางทาง ทีละจุด ตอนที่อนุญาตจุด k เพิ่ม ทางที่ดีที่สุดจาก i ไป j มีได้สองแบบ

ไม่แวะ k ระยะเท่าเดิม d[i][j]
แวะ k ครั้งเดียว คือไป i ถึง k แล้ว k ถึง j โดยแวะได้เฉพาะจุดที่อนุญาตไปก่อนแล้ว ระยะ d[i][k] + d[k][j]

เลือกแบบที่น้อยกว่า พออนุญาตครบทุกจุด d[i][j] ก็คือระยะที่สั้นที่สุดจริง ความคิดแบบนี้คือ dynamic programming จากบทที่ 24 สถานะคือ (i, j, จำนวนจุดที่อนุญาต) และเพราะ d[i][k] กับ d[k][j] ไม่เปลี่ยนระหว่างรอบของ k (แวะ k ระหว่างทางไป k ไม่ช่วยอะไร) จึงเขียนทับตารางเดิมได้ ไม่ต้องเก็บตารางของทุกรอบ

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<long long>> d(n + 1, vector<long long>(n + 1, INF));
    for (int i = 1; i <= n; i++) {
        d[i][i] = 0;
    }
    for (int e = 0; e < m; e++) {
        int u, v, w;
        cin >> u >> v >> w;
        d[u][v] = min(d[u][v], (long long)w); // (1)!
    }
    for (int k = 1; k <= n; k++) { // (2)!
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (d[i][k] + d[k][j] < d[i][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (d[i][j] == INF) {
                cout << "INF";
            } else {
                cout << d[i][j];
            }
            cout << (j == n ? '\n' : ' ');
        }
    }
    return 0;
}

ถ้ามีถนนหลายเส้นระหว่างคู่เดียวกัน เก็บเส้นที่สั้นที่สุด ถ้าเขียนทับเฉยๆ จะได้เส้นที่อ่านทีหลัง ชุดทดสอบชอบดักจุดนี้
k ต้องอยู่ลูปนอกสุด ส่วนลำดับของ i กับ j สลับกันได้

ถนนเป็นทางเดียว แถว i คอลัมน์ j คือระยะจาก i ไป j จาก 1 ไป 2 มีถนนตรงยาว 10 แต่ทาง 1 ไป 3 ไป 4 ไป 2 ยาว 1 + 2 + 3 = 6 ตารางจึงได้ 6 ค่า d[1][2] เปลี่ยนเป็น 6 ตอนรอบ k = 4 เพราะรอบ k = 3 ได้ d[1][4] = 3 ไว้ก่อนแล้ว พอรอบ k = 4 ก็ใช้ d[1][4] + d[4][2] = 3 + 3

ลูปสามชั้น ชั้นละ V รอบ เป็น O(V³) และใช้หน่วยความจำ V² ช่อง ไม่ขึ้นกับจำนวนถนนเลย V = 500 คือ 1.25 × 10⁸ ครั้ง ยังทัน แต่ V = 2000 คือ 8 × 10⁹ ไม่ทันแล้ว

น้ำหนักติดลบกับ Floyd-Warshall

Floyd-Warshall ใช้กับน้ำหนักติดลบได้ ถ้าไม่มีวงติดลบ เพราะไม่ได้อาศัยลำดับแบบ Dijkstra แต่ต้องเพิ่มสองอย่าง

ผ่อนเฉพาะเมื่อ d[i][k] < INF และ d[k][j] < INF เหตุผลเดียวกับหน้า 28.4 อนันต์บวกค่าติดลบจะได้ค่าที่น้อยกว่าอนันต์
หลังจบลูป ถ้ามี i ที่ d[i][i] < 0 แปลว่า i อยู่บนวงติดลบ เพราะเดินออกจาก i แล้ววนกลับมาได้ค่าติดลบ คู่ (a, b) ใดที่มี k ซึ่ง d[a][k] กับ d[k][b] ไม่เป็นอนันต์ และ d[k][k] < 0 คือคู่ที่ระยะลดได้ไม่สิ้นสุด
ระวังค่าล้นเมื่อมีวงติดลบ ช่องที่ติดลบถูกเอามาบวกกันเองซ้ำทุกรอบ k จึงติดลบมากขึ้นเร็วมาก ลองกับกราฟ 70 จุดที่ทุกคู่มีถนนน้ำหนัก -1 ค่าน้อยสุดในตารางคูณราว 6 เท่าทุกรอบ แล้วล้น long long ตั้งแต่รอบ k = 25 หลังจากนั้นค่าในตารางเชื่อไม่ได้ ถ้าโจทย์อาจมีวงติดลบ ให้กันค่าไม่ให้ต่ำกว่า -INF ทุกครั้งที่ผ่อน เช่น d[i][j] = max(d[i][k] + d[k][j], -INF);

เร็วแค่ไหน

อีกวิธีที่ได้ระยะทุกคู่เหมือนกัน คือรัน Dijkstra แบบ priority_queue จากทุกจุด เป็น O(V (V + E) log V) วัดบนเครื่องเดียวกับหน้า 28.1 น้ำหนักสุ่ม 1 ถึง 10⁹ ถนนสองทาง ค่ากลาง 5 รอบ -O2

กราฟ	Floyd-Warshall O(V³)	Dijkstra จากทุกจุด
V = 500 ทุกคู่มีถนน (E = 124750)	0.060 วินาที	0.165 วินาที
V = 1000 ทุกคู่มีถนน (E = 499500)	0.398 วินาที	1.001 วินาที
V = 2000, E = 10000	5.159 วินาที (วัด 3 รอบ)	0.654 วินาที

กราฟที่ทุกคู่มีถนน Floyd-Warshall เร็วกว่าสองเท่าครึ่ง เพราะลูปสามชั้นของมันอ่านตารางเรียงกันในหน่วยความจำ ไม่ต้องยุ่งกับคิว และโค้ดสั้นกว่ามาก แต่กราฟเส้นน้อย Floyd-Warshall ยังต้องทำ V³ ครั้งเท่าเดิม ขณะที่ Dijkstra ทำงานตามจำนวนถนนจริง จึงชนะเกือบแปดเท่า Floyd-Warshall เหมาะกับ V ไม่เกินราว 500 ถึง 1000 ถ้าจุดเยอะกว่านั้นแต่ถนนน้อย ใช้ Dijkstra จากทุกจุดที่ต้องการ

เลือกวิธีตามขอบเขต

ก่อนเขียนโจทย์เส้นทางสั้นสุด ให้ตอบสามคำถามจากโจทย์ น้ำหนักเป็นแบบไหน ต้องการระยะจากจุดเดียวหรือทุกคู่ และ V กับ E ใหญ่แค่ไหน แล้วเลือกจากตาราง

น้ำหนัก	ต้องการ	ขอบเขตที่ใช้ได้	วิธี	เวลา
เท่ากันทุกเส้น	จากจุดเดียว	V, E ถึงหลักล้าน	BFS (บทที่ 27)	O(V + E)
0 หรือ 1	จากจุดเดียว	V, E ถึงหลักล้าน	0-1 BFS (บทที่ 27)	O(V + E)
ไม่ติดลบ	จากจุดเดียว	E ใกล้ V² และ V ไม่เกินหลักพัน	Dijkstra แบบอาเรย์ (หน้า 28.1)	O(V²)
ไม่ติดลบ	จากจุดเดียว	V, E ถึงหลักแสนหรือล้าน	Dijkstra แบบ priority_queue (หน้า 28.2)	O((V + E) log V)
มีติดลบ	จากจุดเดียว หรือตรวจวงติดลบ	V × E ไม่เกินราว 10⁹	Bellman-Ford (หน้า 28.4)	O(VE)
อะไรก็ได้ที่ไม่มีวงติดลบ	ทุกคู่	V ไม่เกินราว 500 ถึง 1000	Floyd-Warshall	O(V³)
ไม่ติดลบ	ทุกคู่ หรือจากหลายจุด	V หลักพัน E น้อย	Dijkstra จากแต่ละจุดที่ต้องการ	O(V (V + E) log V)

มีอีกสามกรณีที่เจอบ่อย

จุดเริ่มหลายจุดแต่ถามแค่ระยะถึงจุดเริ่มที่ใกล้ที่สุด ไม่ต้องรันหลายครั้ง ใส่ทุกจุดเริ่มลงคิวพร้อมกันตามหน้า 28.3
ถามระยะจากทุกจุดไปยัง ปลายทางเดียว กลับทิศถนนทุกเส้นแล้วรัน Dijkstra จากปลายทาง ถนนสองทางไม่ต้องกลับ
กราฟมีทิศทางที่ไม่มีวงเลย (DAG) หาระยะได้ใน O(V + E) แม้มีน้ำหนักติดลบ ด้วยการผ่อนตามลำดับ topological sort ซึ่งจะเรียนในบทที่ 30

ลองทำให้พัง

แบบที่ 1 วางลูป k ไว้ในสุด

หลายคนจำว่า Floyd-Warshall คือลูปสามชั้นที่ใช้ i j k แล้วเขียนเรียงตามตัวอักษร เอา k ไว้ในสุด

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<long long>> d(n + 1, vector<long long>(n + 1, INF));
    for (int i = 1; i <= n; i++) {
        d[i][i] = 0;
    }
    for (int e = 0; e < m; e++) {
        int u, v, w;
        cin >> u >> v >> w;
        d[u][v] = min(d[u][v], (long long)w);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                if (d[i][k] + d[k][j] < d[i][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (d[i][j] == INF) {
                cout << "INF";
            } else {
                cout << d[i][j];
            }
            cout << (j == n ? '\n' : ' ');
        }
    }
    return 0;
}

ผิดสองช่อง d[1][2] ได้ 10 แทน 6 และ d[3][1] ได้ INF ทั้งที่ไปได้ด้วยระยะ 9 ตอนคำนวณช่อง (1, 2) ลูปในสุดลองทุก k แต่ d[1][4] ยังเป็นอนันต์ เพราะช่อง (1, 4) จะคำนวณทีหลังตอน j = 4 แบบนี้แต่ละช่องได้แค่ทางที่ต่อจากสองช่องที่บังเอิญคำนวณเสร็จก่อน ถ้าช่องที่ใช้ต่อเสร็จก่อนจริงก็ได้ทางที่แวะหลายจุด เช่น d[2][4] ได้ 7 ถูกต้อง คือ 2 ไป 1 ไป 3 ไป 4 แวะสองจุด เพราะ d[1][4] ได้ 3 ไปแล้วตั้งแต่แถว i = 1 แต่ถ้าช่องที่ต้องใช้ยังไม่เสร็จ ก็พลาดทางที่ดีที่สุดไปเลย ผลจึงขึ้นกับว่าช่องไหนบังเอิญเสร็จก่อน และคำตอบส่วนใหญ่ยังถูก ตัวอย่างเล็กๆ ในโจทย์จึงมักผ่าน จำว่า k คือจุดแวะ ต้องอยู่นอกสุด

แบบที่ 2 ใช้ LLONG_MAX เป็นอนันต์

ในโปรแกรม floyd เปลี่ยนอนันต์เป็น const long long INF = LLONG_MAX; เพราะคิดว่าใหญ่ที่สุดย่อมปลอดภัยที่สุด

#include <bits/stdc++.h>
using namespace std;

const long long INF = LLONG_MAX;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<long long>> d(n + 1, vector<long long>(n + 1, INF));
    for (int i = 1; i <= n; i++) {
        d[i][i] = 0;
    }
    for (int e = 0; e < m; e++) {
        int u, v, w;
        cin >> u >> v >> w;
        d[u][v] = min(d[u][v], (long long)w);
    }
    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] + d[k][j] < d[i][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (d[i][j] == INF) {
                cout << "INF";
            } else {
                cout << d[i][j];
            }
            cout << (j == n ? '\n' : ' ');
        }
    }
    return 0;
}

-9223372036854775794 -9223372036854775798 -9223372036854775807 -9223372036854775797
-9223372036854775790 -9223372036854775794 -9223372036854775803 -9223372036854775807
-9223372036854775797 -9223372036854775801 -9223372036854775808 -4
-9223372036854775797 -9223372036854775801 -9223372036854775808 -4

ตารางพังทั้งตาราง รอบ k = 1 ตอนคำนวณช่อง (2, 4) ซึ่งยังไม่มีถนน โปรแกรมลอง d[2][1] + d[1][4] คือ 4 + LLONG_MAX ล้นเป็นค่าติดลบที่เกือบน้อยที่สุดของ long long ค่านั้นน้อยกว่าอนันต์จึงถูกเก็บ แล้วรอบต่อๆ ไปค่าติดลบก็ลามไปทุกช่องที่ใช้มันต่อ Floyd-Warshall บวกระยะสองช่องที่อาจเป็นอนันต์ทั้งคู่ จึงต้องเลือกอนันต์ที่บวกกันสองตัวแล้วยังไม่ล้น 10¹⁸ บวกกันได้ 2 × 10¹⁸ ยังน้อยกว่าขีดจำกัด หรือเช็ก < INF ก่อนบวกทุกครั้ง

สรุป

Floyd-Warshall ให้ระยะทุกคู่ด้วยลูปสามชั้น d[i][j] = min(d[i][j], d[i][k] + d[k][j]) เป็น O(V³) ใช้กับ V ไม่เกินราว 500 ถึง 1000
k คือจุดแวะ ต้องอยู่ลูปนอกสุด วางผิดที่แล้วคำตอบผิดบางช่องโดยไม่มีอะไรเตือน
เริ่มตารางด้วย 0 บนเส้นทแยง ถนนซ้ำคู่เก็บเส้นที่สั้นที่สุด และใช้อนันต์ 10¹⁸ ที่บวกกันสองตัวแล้วไม่ล้น
รับน้ำหนักติดลบได้ถ้าเช็ก < INF ก่อนบวก และ d[i][i] < 0 บอกว่า i อยู่บนวงติดลบ เมื่อมีวงติดลบค่าติดลบโตเร็วมากจนล้นได้ ให้กันไม่ให้ต่ำกว่า -INF
ก่อนเขียน ดูชนิดของน้ำหนัก จุดเดียวหรือทุกคู่ และขนาด V กับ E แล้วเลือกจากตารางในหน้านี้

กลับไปเช็กรายการ ผ่านบทนี้เมื่อ แล้วไปทำแบบฝึกหัด