[0]zero-index clytie0x/zero-index

28.4 น้ำหนักติดลบและ Bellman-Ford

บางโจทย์มีน้ำหนักติดลบ เช่น รถขนของที่วิ่งเปล่าบางเส้นต้องจ่ายค่าน้ำมัน แต่บางเส้นได้ค่าจ้างขนสินค้ากลับ ค่าใช้จ่ายของเส้นนั้นจึงติดลบ หรือเกมที่บางห้องหักพลัง บางห้องเติมพลัง หน้า 28.1 พิสูจน์ว่า Dijkstra ถูกโดยอาศัยว่าน้ำหนักไม่ติดลบ หน้านี้แสดงว่าพอเงื่อนไขนั้นหายไป Dijkstra ผิดจริง แล้วใช้วิธีที่ช้ากว่าแต่รับน้ำหนักติดลบได้ ชื่อ Bellman-Ford ซึ่งยังตรวจได้ด้วยว่ามีวงที่วนแล้วค่าใช้จ่ายลดลงเรื่อยๆ ไม่สิ้นสุดหรือไม่

ทุกตัวอย่างในหน้านี้เป็นกราฟมีทิศทาง (directed) ถนน u v w แปลว่าวิ่งจาก u ไป v ได้ทางเดียว เหตุผลอยู่ในส่วนลองทำให้พัง

Dijkstra ผิดเมื่อมีน้ำหนักติดลบ

ใช้ Dijkstra แบบอาเรย์จากหน้า 28.1 เปลี่ยนแค่ให้ถนนเป็นทางเดียว แผนที่มีสี่จุด ถนนจาก 3 ไป 2 ได้ค่าจ้างกลับ 4 บาท

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

const long long INF = 1e18;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w}); // (1)!
    }
    vector<long long> dist(n + 1, INF);
    vector<bool> done(n + 1, false);
    dist[1] = 0;
    for (int round = 0; round < n; round++) {
        int u = -1;
        for (int i = 1; i <= n; i++) {
            if (!done[i] && (u == -1 || dist[i] < dist[u])) {
                u = i;
            }
        }
        if (dist[u] == INF) {
            break;
        }
        done[u] = true;
        cout << "take " << u << " dist=" << dist[u] << '\n';
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
    }
    for (int u = 1; u <= n; u++) {
        cout << dist[u] << (u == n ? '\n' : ' ');
    }
    return 0;
}
  1. ถนนทางเดียว ใส่เฉพาะ adj[u]
4 4
1 2 2
1 3 5
3 2 -4
2 4 3

take 1 dist=0
take 2 dist=2
take 3 dist=5
take 4 dist=5
0 1 5 5

ทางที่ถูกคือ 1 ไป 3 ไป 2 ไป 4 ค่าใช้จ่าย 5 - 4 + 3 = 4 แต่โปรแกรมตอบ 5 จุด 2 ถูกเลือกเป็นจุดที่เสร็จตั้งแต่ระยะ 2 และผ่อนถนนไปจุด 4 ได้ 5 ทีหลังจุด 3 ผ่อนกลับมาลดจุด 2 เหลือ 1 แต่จุด 2 เสร็จไปแล้ว ไม่มีใครส่งค่าใหม่ต่อให้จุด 4 คำตอบจึงขัดกันเอง จุด 2 บอก 1 แต่จุด 4 ยังคิดจากจุด 2 ที่ระยะ 2

เหตุผลในหน้า 28.1 พังตรงประโยค "เดินจาก x ต่อไปถึง u ซึ่งไม่ทำให้ระยะลดลง" ทางที่ผ่านจุด 3 ซึ่งตอนนั้นไกลกว่า กลับมาถูกลงได้ด้วยถนนติดลบ จุดที่ใกล้ที่สุดในตอนนั้นจึงยังไม่ใช่คำตอบสุดท้าย

แบบ priority_queue บังเอิญรอด แต่ไม่ปลอดภัย

ข้อมูลชุดนี้ป้อนให้แบบ priority_queue ในหน้า 28.2 ที่ทำเป็นทางเดียว ได้ 0 1 5 4 ถูก เพราะพอจุด 2 ได้ระยะใหม่ ก็ถูกใส่ลงคิวและถูกหยิบมาทำซ้ำ แต่นั่นไม่ใช่ Dijkstra แล้ว จุดเดียวกันอาจถูกทำซ้ำได้มากจนไม่มีขอบเขตเวลาที่รับประกัน และถ้ามีวงติดลบในหัวข้อถัดไป ระยะจะลดลงไม่หยุด ลองแล้วโปรแกรมพิมพ์ระยะที่ติดลบมากขึ้นเรื่อยๆ จนต้องหยุดเองเมื่อครบสิบวินาที โจทย์ที่มีน้ำหนักติดลบให้ใช้วิธีในหน้านี้

Bellman-Ford

ความคิดง่ายมาก ผ่อนถนนทุกเส้น วนแบบนี้ V - 1 รอบ ไม่ต้องสนลำดับ ไม่ต้องมีคิว ไม่ต้องเก็บ adjacency list เก็บแค่รายการถนนสามอาเรย์ก็พอ

ทำไม V - 1 รอบพอ ถ้าไม่มีวงติดลบ ทางที่สั้นที่สุดไม่จำเป็นต้องผ่านจุดซ้ำ เพราะวงที่ไม่ติดลบตัดทิ้งได้โดยไม่ทำให้ยาวขึ้น ทางที่สั้นที่สุดจึงมีไม่เกิน V - 1 เส้น ให้ทางที่สั้นที่สุดถึง v เป็น 1 = x0, x1, ..., xk = v รอบที่ 1 ผ่อนถนนทุกเส้น ซึ่งรวมถนน x0 ไป x1 ด้วย dist[x1] จึงถูกแล้ว รอบที่ 2 ผ่อนถนน x1 ไป x2 ด้วย dist[x1] ที่ถูกแล้ว dist[x2] จึงถูก ไล่ไปเรื่อยๆ หลังรอบที่ k dist[v] ถูกแน่นอน และ k ไม่เกิน V - 1

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

const long long INF = 1e18;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> from(m), to(m), cost(m); // (1)!
    for (int i = 0; i < m; i++) {
        cin >> from[i] >> to[i] >> cost[i];
    }
    vector<long long> dist(n + 1, INF);
    dist[1] = 0;
    for (int round = 1; round <= n - 1; round++) { // (2)!
        bool changed = false;
        for (int i = 0; i < m; i++) {
            int u = from[i], v = to[i];
            if (dist[u] != INF && dist[u] + cost[i] < dist[v]) { // (3)!
                dist[v] = dist[u] + cost[i];
                changed = true;
            }
        }
        cout << "after round " << round << ":";
        for (int u = 1; u <= n; u++) {
            if (dist[u] == INF) {
                cout << " inf";
            } else {
                cout << ' ' << dist[u];
            }
        }
        cout << '\n';
        if (!changed) { // (4)!
            break;
        }
    }
    return 0;
}
  1. เก็บถนนเป็นรายการ เส้นที่ i วิ่งจาก from[i] ไป to[i] ค่าใช้จ่าย cost[i]
  2. วนไม่เกิน V - 1 รอบ แต่ละรอบผ่อนถนนครบทุกเส้น
  3. ผ่อนเฉพาะถนนที่ต้นทางไปถึงแล้ว เหตุผลอยู่ในส่วนลองทำให้พัง
  4. รอบไหนไม่มีอะไรเปลี่ยน รอบต่อไปก็ไม่มีอะไรเปลี่ยนเหมือนกัน เพราะผ่อนด้วยค่าชุดเดิม หยุดได้เลย
4 4
2 4 3
3 2 -4
1 3 5
1 2 2

after round 1: 0 2 5 inf
after round 2: 0 1 5 5
after round 3: 0 1 5 4

กราฟเดิม แต่เรียงถนนกลับด้าน รอบที่ 1 ถนนที่ออกจากจุด 2 กับจุด 3 ถูกผ่อนก่อนที่สองจุดนี้จะไปถึงได้ จึงไม่เกิดอะไร ได้แค่ระยะของถนนที่ออกจากจุด 1 รอบที่ 2 ได้ทางที่มีสองเส้น จุด 2 ลดเป็น 1 รอบที่ 3 ได้ทางที่มีสามเส้น จุด 4 เป็น 4 ถูกต้อง ลำดับของถนนมีผลกับจำนวนรอบที่ต้องใช้จริง แต่ไม่มีผลกับคำตอบ เพราะ V - 1 รอบพอเสมอ ถ้าเรียงถนนตามลำดับเดิมในหัวข้อก่อน รอบแรกก็ได้ 0 1 5 4 ครบแล้ว

แต่ละรอบดูถนน E เส้น วนไม่เกิน V - 1 รอบ จึงเป็น O(VE) ช้ากว่า Dijkstra มาก แลกกับการรับน้ำหนักติดลบได้

วงติดลบ

ถ้ามีวงที่ผลรวมน้ำหนักติดลบ เช่น วิ่ง 2 ไป 3 ไป 4 แล้วกลับ 2 ได้กำไรรอบละ 1 บาท ก็วนวงนี้กี่รอบก็ได้ ค่าใช้จ่ายลดลงไม่มีที่สิ้นสุด ทางที่สั้นที่สุดจึงไม่มีอยู่จริงสำหรับทุกจุดที่ไปถึงได้หลังผ่านวงนี้ โจทย์มักให้ตอบว่า "ลดได้ไม่สิ้นสุด" สำหรับจุดเหล่านั้น

ตรวจด้วยข้อสังเกตจากหัวข้อก่อน ถ้าไม่มีวงติดลบ หลัง V - 1 รอบจะไม่มีถนนไหนผ่อนได้อีก ถ้ารอบที่ V ยังผ่อนได้ แปลว่ามีวงติดลบที่ไปถึงจากจุดเริ่มได้แน่นอน ส่วนจุดที่ได้รับผลกระทบ คือจุดที่ยังผ่อนได้ กับทุกจุดที่เดินต่อจากจุดพวกนั้นได้ วนผ่อนอีก V รอบพร้อมส่งเครื่องหมายต่อไปตามถนน ก็ทั่วถึงทุกจุด

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

const long long INF = 1e18;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> from(m), to(m), cost(m);
    for (int i = 0; i < m; i++) {
        cin >> from[i] >> to[i] >> cost[i];
    }
    vector<long long> dist(n + 1, INF);
    dist[1] = 0;
    for (int round = 1; round <= n - 1; round++) {
        for (int i = 0; i < m; i++) {
            int u = from[i], v = to[i];
            if (dist[u] != INF && dist[u] + cost[i] < dist[v]) {
                dist[v] = dist[u] + cost[i];
            }
        }
    }
    vector<bool> endless(n + 1, false);
    for (int round = 1; round <= n; round++) { // (1)!
        for (int i = 0; i < m; i++) {
            int u = from[i], v = to[i];
            if (dist[u] == INF) {
                continue;
            }
            if (endless[u] || dist[u] + cost[i] < dist[v]) { // (2)!
                endless[v] = true;
                dist[v] = min(dist[v], dist[u] + cost[i]);
            }
        }
    }
    for (int u = 1; u <= n; u++) {
        cout << u << ": ";
        if (dist[u] == INF) {
            cout << "unreachable" << '\n';
        } else if (endless[u]) {
            cout << "-inf" << '\n';
        } else {
            cout << dist[u] << '\n';
        }
    }
    return 0;
}
  1. หลัง V - 1 รอบแรก วนต่ออีก V รอบ เครื่องหมายเดินได้รอบละอย่างน้อยหนึ่งเส้น V รอบจึงไปถึงทุกจุดที่ไปถึงได้
  2. ปลายถนนได้รับผลกระทบถ้ายังผ่อนได้ หรือต้นถนนได้รับผลกระทบอยู่แล้ว
8 8
1 2 4
2 3 -2
3 4 3
4 2 -2
4 5 1
1 6 5
6 5 2
7 8 -3

1: 0
2: -inf
3: -inf
4: -inf
5: -inf
6: 5
7: unreachable
8: unreachable

วง 2 3 4 รวม -2 + 3 - 2 = -1 จุด 2 3 4 จึงได้ -inf จุด 5 ไปถึงได้จากจุด 4 จึงได้ด้วย ส่วนจุด 6 ไปได้แค่จากจุด 1 โดยตรง ไม่ผ่านวง จึงได้ 5 ตามปกติ จุด 7 กับ 8 ไม่มีทางไปจากจุด 1 เลย

หาวงติดลบที่ไหนก็ได้ในกราฟ

โปรแกรมนี้สนใจเฉพาะวงที่ไปถึงจากจุด 1 ได้ ถ้าโจทย์ถามว่า "มีวงติดลบอยู่ที่ใดในกราฟหรือไม่" ให้เริ่มทุกจุดที่ dist เป็น 0 แทนอนันต์ เหมือนมีจุดเริ่มสมมติที่มีถนนยาว 0 ไปทุกจุด แบบหลายจุดเริ่มในหน้า 28.3 แล้วดูว่ารอบที่ V ยังผ่อนได้หรือไม่

เร็วแค่ไหน

วิธีตรงไปตรงมาที่รับน้ำหนักติดลบได้คือลองทุกเส้นทางแบบหน้า 28.1 ซึ่งที่ 14 จุดก็ใช้เวลาเป็นสิบวินาทีแล้ว Bellman-Ford ช้ากว่า Dijkstra แต่ยังอยู่ในระดับพหุนาม วัดบนเครื่องเดียวกับหน้า 28.1 กราฟสุ่มที่มีถนนติดลบแต่ไม่มีวงติดลบ สร้างโดยสุ่มความสูง h ให้ทุกจุด แล้วให้ถนน u ไป v มีค่า สุ่มบวก + h[u] - h[v] วงใดๆ ผลรวมของ h หักล้างกันหมด จึงเหลือแต่ส่วนที่เป็นบวก แถวที่เป็นเส้นยาวคือกราฟที่ทางที่สั้นที่สุดไปจุดสุดท้ายผ่านทุกจุดเรียงกัน และถนนเส้นนั้นอยู่ในรายการกลับด้าน ค่ากลาง 5 รอบ -O2

กราฟแบบจำนวนรอบที่วนเวลา
V = 104, E = 5 × 104สุ่ม วนครบ V - 1 รอบ99990.297 วินาที
สุ่ม หยุดเมื่อไม่เปลี่ยน120.001 วินาที
เส้นยาว หยุดเมื่อไม่เปลี่ยน99990.280 วินาที
V = 105, E = 2 × 105สุ่ม หยุดเมื่อไม่เปลี่ยน100.003 วินาที
เส้นยาว หยุดเมื่อไม่เปลี่ยน9999912.253 วินาที (วัด 3 รอบ)

กราฟสุ่มทางที่สั้นที่สุดมีแค่สิบกว่าเส้น การหยุดเมื่อไม่มีอะไรเปลี่ยนจึงจบเร็วมาก แต่ชุดทดสอบที่ตั้งใจดักจะให้ทางยาวแบบแถวเส้นยาว ซึ่งต้องวนเกือบครบ V - 1 รอบ ที่ V เป็นแสนใช้กว่าสิบวินาที ขณะที่ Dijkstra กับกราฟขนาดเดียวกันในหน้า 28.2 ใช้ไม่ถึงหนึ่งในสิบวินาที จึงประเมินเวลาด้วย V × E เสมอ ลูปของ Bellman-Ford เรียบง่ายมาก แถวแรกที่ V × E เป็น 5 × 108 ยังใช้ราว 0.3 วินาที แต่ถ้าเกินระดับ 109 ให้ดูว่าโจทย์มีน้ำหนักติดลบจริงหรือไม่

ลองทำให้พัง

แบบที่ 1 ผ่อนจากจุดที่ไปไม่ถึง

ในโปรแกรม bf-cycle ลบ dist[u] != INF && ออกจากการผ่อน V - 1 รอบแรก เพราะคิดว่าอนันต์บวกอะไรก็ยังมากกว่าค่าอื่น

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

const long long INF = 1e18;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> from(m), to(m), cost(m);
    for (int i = 0; i < m; i++) {
        cin >> from[i] >> to[i] >> cost[i];
    }
    vector<long long> dist(n + 1, INF);
    dist[1] = 0;
    for (int round = 1; round <= n - 1; round++) {
        for (int i = 0; i < m; i++) {
            int u = from[i], v = to[i];
            if (dist[u] + cost[i] < dist[v]) {
                dist[v] = dist[u] + cost[i];
            }
        }
    }
    vector<bool> endless(n + 1, false);
    for (int round = 1; round <= n; round++) { // (1)!
        for (int i = 0; i < m; i++) {
            int u = from[i], v = to[i];
            if (dist[u] == INF) {
                continue;
            }
            if (endless[u] || dist[u] + cost[i] < dist[v]) { // (2)!
                endless[v] = true;
                dist[v] = min(dist[v], dist[u] + cost[i]);
            }
        }
    }
    for (int u = 1; u <= n; u++) {
        cout << u << ": ";
        if (dist[u] == INF) {
            cout << "unreachable" << '\n';
        } else if (endless[u]) {
            cout << "-inf" << '\n';
        } else {
            cout << dist[u] << '\n';
        }
    }
    return 0;
}

8 8
1 2 4
2 3 -2
3 4 3
4 2 -2
4 5 1
1 6 5
6 5 2
7 8 -3

1: 0
2: -inf
3: -inf
4: -inf
5: -inf
6: 5
7: unreachable
8: 999999999999999997

จุด 8 ไปไม่ถึงจากจุด 1 แต่ได้ระยะเป็นเลขยาวเหยียด เพราะถนน 7 ไป 8 ค่า -3 ทำให้ INF - 3 น้อยกว่า INF จึงถูกเก็บ พอตรวจตอนพิมพ์ว่าเท่ากับ INF หรือไม่ ก็ไม่เท่า ข้อนี้เกิดเฉพาะเมื่อมีน้ำหนักติดลบ Dijkstra ในหน้าก่อนๆ ไม่เคยเจอ เพราะไม่เคยหยิบจุดที่ไปไม่ถึงออกมาผ่อน ถ้าถนนที่ออกจากจุดที่ไปไม่ถึงมีค่าเป็นบวกและใช้ INT_MAX หรือ LLONG_MAX เป็นอนันต์ ก็จะล้นเป็นค่าติดลบแบบหน้า 28.1

แบบที่ 2 ถนนสองทางที่ติดลบ

ถ้าโจทย์ให้ถนนวิ่งได้สองทางแล้วใส่ทั้งสองทิศลงรายการ ถนนที่ติดลบแค่เส้นเดียวก็คือวงติดลบแล้ว เพราะวิ่งไปกลับบนถนนเส้นนั้นได้กำไรทุกเที่ยว ป้อนให้โปรแกรม bf-cycle โดยถนน 2 กับ 3 ค่า -1 วิ่งได้สองทาง

3 4
1 2 5
2 1 5
2 3 -1
3 2 -1

1: -inf
2: -inf
3: -inf

ทุกจุดเป็น -inf รวมทั้งจุดเริ่มเอง เพราะไปจุด 2 แล้ววนกลับมาได้ น้ำหนักติดลบจึงมีความหมายเฉพาะกับกราฟมีทิศทาง กราฟไม่มีทิศทางที่มีถนนติดลบ คำตอบเป็น -inf ทุกจุดที่ไปถึงถนนเส้นนั้นได้ ต้องอ่านโจทย์ให้ชัดว่าถนนเป็นทางเดียวหรือสองทาง

สรุป

  • Dijkstra ถูกเฉพาะเมื่อน้ำหนักไม่ติดลบ ถ้ามีถนนติดลบ คำตอบผิดได้ และแบบ priority_queue ไม่มีเวลาที่รับประกัน
  • Bellman-Ford ผ่อนถนนทุกเส้น V - 1 รอบ เป็น O(VE) หยุดก่อนได้เมื่อรอบไหนไม่มีอะไรเปลี่ยน
  • ผ่อนเฉพาะถนนที่ต้นทางไปถึงแล้ว dist[u] != INF
  • ถ้ารอบที่ V ยังผ่อนได้ มีวงติดลบ วนต่ออีก V รอบเพื่อส่งเครื่องหมายไปทุกจุดที่ได้รับผลกระทบ
  • ถนนสองทางที่ติดลบคือวงติดลบในตัวมันเอง