28.1 BFS ไม่พอ และ Dijkstra แบบอาเรย์

บทที่ 27 ใช้ BFS หาระยะทางที่สั้นที่สุดเมื่อทุกเส้นยาวเท่ากัน ถนนจริงไม่เป็นแบบนั้น ถนนบางเส้นใช้เวลา 2 นาที บางเส้นใช้ 15 นาที ค่าโดยสารแต่ละช่วงก็ไม่เท่ากัน โจทย์ที่ถามว่า "ไปจากจุดหนึ่งถึงอีกจุดหนึ่งใช้เวลาหรือค่าใช้จ่ายน้อยที่สุดเท่าไร" ออกในค่าย 2 และ TOI แทบทุกปี หน้านี้แสดงให้เห็นก่อนว่าทำไม BFS ตอบผิด แล้วเขียนวิธีที่ถูกที่ชื่อ Dijkstra (อ่านว่า ไดค์สตรา ตามชื่อนักวิทยาศาสตร์คอมพิวเตอร์ชาวดัตช์) แบบที่ใช้อาเรย์ธรรมดา

กราฟมีน้ำหนัก

กราฟที่ทุกเส้นมีตัวเลขกำกับเรียกว่า กราฟมีน้ำหนัก (weighted graph) ตัวเลขนั้นคือ น้ำหนัก (weight) จะแทนระยะทาง เวลา หรือค่าใช้จ่ายก็ได้ ความยาวของเส้นทางคือผลรวมน้ำหนักของทุกเส้นที่ผ่าน ไม่ใช่จำนวนเส้น ตลอดหน้านี้ใช้แผนที่เมืองเล็กๆ ที่มี 6 จุด ตัวเลขบนถนนคือเวลาเดินทางเป็นนาที และถนนทุกเส้นวิ่งได้สองทาง

ข้อมูลเข้าของกราฟแบบนี้ บรรทัดแรกคือจำนวนจุด n กับจำนวนถนน m แล้วตามด้วยถนนบรรทัดละเส้น เป็นจุดปลายสองข้าง u v กับน้ำหนัก w เก็บด้วย adjacency list แบบบทที่ 27 ต่างกันแค่แต่ละช่องเก็บเป็นคู่ (ปลายทาง, น้ำหนัก) แทนที่จะเก็บแค่ปลายทาง

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

int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> adj(n + 1); // (1)!
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    for (int u = 1; u <= n; u++) {
        cout << u << ":";
        for (auto [v, w] : adj[u]) { // (2)!
            cout << " (" << v << ", " << w << ")";
        }
        cout << '\n';
    }
    return 0;
}

adj[u] คือรายชื่อถนนที่ออกจากจุด u แต่ละตัวเป็น pair ช่องแรกคือปลายทาง ช่องที่สองคือน้ำหนัก ถนนสองทางจึงใส่ทั้ง adj[u] และ adj[v]
แตก pair ออกเป็น v กับ w ด้วย structured binding จากหน้า 16.4 อ่านง่ายกว่า .first กับ .second

1: (2, 4) (3, 1)
2: (1, 4) (3, 2) (4, 5)
3: (1, 1) (2, 2) (4, 8) (5, 10)
4: (2, 5) (3, 8) (5, 2) (6, 6)
5: (3, 10) (4, 2) (6, 3)
6: (4, 6) (5, 3)

ทำไม BFS ตอบผิด

ลองเอา BFS จากบทที่ 27 มาใช้ตรงๆ เปลี่ยนแค่ตอนเจอจุดใหม่ ให้ระยะของจุดนั้นเป็นระยะของจุดก่อนหน้าบวกน้ำหนักของถนน แทนที่จะบวกหนึ่ง

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

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});
        adj[v].push_back({u, w});
    }
    vector<long long> dist(n + 1, -1);
    queue<int> q;
    dist[1] = 0;
    q.push(1);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (auto [v, w] : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + w;
                q.push(v);
            }
        }
    }
    for (int u = 1; u <= n; u++) {
        cout << dist[u] << (u == n ? '\n' : ' ');
    }
    return 0;
}

0 4 1 9 11 15

ดูจุดที่ 2 ตลาด BFS ตอบ 4 เพราะเจอตลาดครั้งแรกจากถนนตรงที่ยาว 4 นาที แต่ทางอ้อม บ้าน วัด ตลาด ใช้แค่ 1 + 2 = 3 นาที พอตลาดผิด ทุกจุดที่ BFS ไปเจอผ่านตลาดก็ผิดตามกันหมด คำตอบที่ถูกคือ 0 3 1 8 10 13 ผิดไปสี่จุดจากหกจุด

BFS รับประกันแค่ว่าจุดที่เจอก่อนอยู่ห่างจากจุดเริ่ม จำนวนเส้น น้อยกว่าหรือเท่ากัน ซึ่งเท่ากับระยะทางจริงเฉพาะตอนที่ทุกเส้นยาวเท่ากัน พอเส้นยาวไม่เท่ากัน ทางที่ผ่านสองเส้นสั้นๆ อาจสั้นกว่าเส้นยาวเส้นเดียว 0-1 BFS ในบทที่ 27 แก้ได้เฉพาะกรณีที่น้ำหนักเป็น 0 กับ 1 เท่านั้น น้ำหนักทั่วไปต้องใช้วิธีในบทนี้

ผ่อนระยะ

ทุกวิธีในบทนี้ใช้การกระทำพื้นฐานอย่างเดียวกัน ให้ dist[v] คือระยะที่สั้นที่สุดเท่าที่รู้ตอนนี้จากจุดเริ่มถึง v เริ่มต้นจุดเริ่มเป็น 0 จุดอื่นเป็นค่าที่ใหญ่มากแทนอนันต์ เมื่อดูถนนจาก u ไป v ที่ยาว w ถ้า dist[u] + w น้อยกว่า dist[v] แปลว่าเจอทางไป v ที่สั้นกว่าเดิม คือไปถึง u ก่อนแล้วต่อถนนเส้นนี้ ให้แก้ dist[v] เป็นค่าใหม่

if (dist[u] + w < dist[v])
    dist[v] = dist[u] + w

การทำแบบนี้เรียกว่า relaxation แปลตรงตัวว่าผ่อน เพราะค่าใน dist ลดลงเรื่อยๆ จนถึงค่าจริง ไม่มีวันต่ำกว่าค่าจริง เพราะทุกค่าที่ใส่ลงไปคือความยาวของเส้นทางที่มีอยู่จริงเส้นหนึ่ง สิ่งที่ทำให้แต่ละวิธีในบทนี้ต่างกันคือ ลำดับ ของการผ่อน ผ่อนถูกลำดับก็ทำครั้งเดียวพอ ผ่อนผิดลำดับต้องทำซ้ำหลายรอบ

ความคิดของ Dijkstra

แบ่งจุดเป็นสองกลุ่ม กลุ่มที่ เสร็จแล้ว คือรู้ระยะจริงแน่นอน กับกลุ่มที่ยังไม่เสร็จ ทุกรอบทำสองอย่าง

เลือกจุด u ที่ยังไม่เสร็จและมี dist น้อยที่สุด แล้วประกาศว่า u เสร็จ
ผ่อนทุกถนนที่ออกจาก u

ทำไมจุดที่เลือกเสร็จได้ทันที

สมมติ u มี dist น้อยที่สุดในกลุ่มที่ยังไม่เสร็จ เส้นทางอื่นที่จะไปถึง u ได้ ต้องออกจากกลุ่มที่เสร็จแล้วไปที่จุด x สักจุดในกลุ่มที่ยังไม่เสร็จก่อน ระยะถึง x อย่างน้อยก็ dist[x] ซึ่งไม่น้อยกว่า dist[u] แล้วยังต้องเดินจาก x ต่อไปถึง u ซึ่งไม่ทำให้ระยะลดลง เพราะน้ำหนักไม่ติดลบ จึงไม่มีทางไหนสั้นกว่า dist[u] อีกแล้ว เงื่อนไขตัวหนาข้อนี้สำคัญมาก หน้า 28.4 จะแสดงว่าถ้ามีน้ำหนักติดลบ เหตุผลนี้พังทันที

ลองกับแผนที่เมือง เริ่มที่บ้าน ตารางแสดงค่า dist หลังจบแต่ละรอบ ช่องที่เป็นตัวหนาคือจุดที่เพิ่งเลือกในรอบนั้น ∞ คือยังไม่เจอทางไป

รอบ	เลือก	2	3	4	5	6
เริ่ม		∞	∞	∞	∞	∞
1	1	4	1	∞	∞	∞
2	3	3	1	9	11	∞
3	2	3	1	8	11	∞
4	4	3	1	8	10	14
5	5	3	1	8	10	13
6	6	3	1	8	10	13

รอบที่ 2 เลือกวัดเพราะ 1 น้อยกว่า 4 ของตลาด แล้วผ่อนถนนวัดไปตลาด ได้ 1 + 2 = 3 ดีกว่า 4 เดิม ตรงนี้คือจุดที่ BFS พลาด BFS ตัดสินตลาดไปแล้วตั้งแต่เห็นครั้งแรก ส่วน Dijkstra รอจนตลาดเป็นจุดที่ใกล้ที่สุดที่เหลืออยู่ก่อน ค่อยตัดสิน สังเกตว่าจุดที่ถูกเลือกมีระยะ 0 1 3 8 10 13 เรียงจากน้อยไปมากเสมอ Dijkstra ขยายวงออกจากจุดเริ่มตามระยะทางจริง เหมือนที่ BFS ขยายวงตามจำนวนเส้น

เขียนด้วยอาเรย์

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

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

const long long INF = 1e18; // (1)!

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});
        adj[v].push_back({u, w});
    }
    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++) { // (2)!
            if (!done[i] && (u == -1 || dist[i] < dist[u])) {
                u = i;
            }
        }
        if (dist[u] == INF) { // (3)!
            break;
        }
        done[u] = true;
        cout << "take " << u << " dist=" << dist[u] << '\n';
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) { // (4)!
                dist[v] = dist[u] + w;
            }
        }
    }
    for (int u = 1; u <= n; u++) {
        if (dist[u] == INF) {
            cout << -1 << (u == n ? '\n' : ' ');
        } else {
            cout << dist[u] << (u == n ? '\n' : ' ');
        }
    }
    return 0;
}

ใช้ 10¹⁸ แทนอนันต์ ระยะจริงในโจทย์ส่วนใหญ่ไม่เกินราว 10¹⁴ (แสนเส้น เส้นละ 10⁹) และ 10¹⁸ บวกน้ำหนักอีกเส้นก็ยังไม่ล้น long long ซึ่งเก็บได้ถึงราว 9 × 10¹⁸ ตามหน้า 1.3 ส่วน 1e18 คือวิธีเขียน 1 × 10¹⁸ แบบวิทยาศาสตร์ที่เห็นในหน้า 15.2 เขียนแบบนี้แล้วได้ค่าเป็น double แต่ 10¹⁸ เป็นค่าที่ double เก็บได้ตรงทุกหลัก พอใส่ลงตัวแปร long long จึงได้ 1000000000000000000 พอดี และพิมพ์ง่ายกว่านับเลขศูนย์สิบแปดตัว
ไล่หาจุดที่ยังไม่เสร็จที่ dist น้อยที่สุด รอบละ n ช่อง
จุดที่น้อยที่สุดยังเป็นอนันต์ แปลว่าจุดที่เหลือทั้งหมดไปไม่ถึง หยุดได้เลย
ผ่อนถนนที่ออกจาก u ตามหัวข้อก่อนหน้า

take 1 dist=0
take 3 dist=1
take 2 dist=3
take 4 dist=8
take 5 dist=10
take 6 dist=13
0 3 1 8 10 13

ลำดับที่เลือกตรงกับตาราง แต่ละรอบไล่หาจุดน้อยที่สุด n ช่อง ทำ n รอบ เป็น O(V²) เมื่อ V คือจำนวนจุด (vertex) ส่วนการผ่อนถนน แต่ละจุดผ่อนถนนของตัวเองครั้งเดียวตอนที่ถูกเลือก ถนนสองทางถูกผ่อนจากทั้งสองข้าง จึงรวมราว 2E ครั้งเมื่อ E คือจำนวนเส้น (edge) ทั้งหมดเป็น O(V² + E)

เร็วขึ้นแค่ไหน

ถ้าไม่รู้จัก Dijkstra วิธีตรงไปตรงมาคือ backtracking แบบบทที่ 21 ลองเดินทุกเส้นทางที่ไม่ซ้ำจุดจากจุด 1 ไปจุด n แล้วจำเส้นที่สั้นที่สุดไว้ วัดบนโน้ตบุ๊ก ASUS Vivobook S 14 ซีพียู AMD Ryzen AI 9 HX 370 Windows 11 เสียบสายชาร์จ คอมไพล์ด้วย GCC 14.2 ของ Code::Blocks แบบ -O2 กราฟคือ n จุดที่ทุกคู่มีถนนถึงกัน น้ำหนักสุ่ม 1 ถึง 100 จับเวลาเฉพาะช่วงหาคำตอบ แต่ละช่องเป็นค่ากลางของ 5 รอบ

n	ลองทุกเส้นทาง	Dijkstra แบบอาเรย์
12	0.093 วินาที	0.000 วินาที
13	1.325 วินาที	0.000 วินาที
14	15.237 วินาที (วัด 3 รอบ)	0.000 วินาที
3000	ไม่ได้วัด	0.022 วินาที

เพิ่มจุดทีละหนึ่ง วิธีลองทุกเส้นทางช้าลงกว่าสิบเท่าทุกครั้ง เพราะจำนวนเส้นทางที่ไม่ซ้ำจุดโตแบบแฟกทอเรียลตามหน้า 18.2 ส่วน Dijkstra ที่ 3000 จุด ซึ่งมีถนนเกือบสี่ล้านครึ่งเส้น ยังใช้ไม่ถึงหนึ่งในสิบวินาที

ลองทำให้พัง

แบบที่ 1 ลืมเช็กว่าเสร็จแล้ว

ในโปรแกรม dijkstra-array ลบ !done[i] && ออกจากเงื่อนไขที่หาจุดน้อยที่สุด

#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});
        adj[v].push_back({u, w});
    }
    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 (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++) {
        if (dist[u] == INF) {
            cout << -1 << (u == n ? '\n' : ' ');
        } else {
            cout << dist[u] << (u == n ? '\n' : ' ');
        }
    }
    return 0;
}

take 1 dist=0
take 1 dist=0
take 1 dist=0
take 1 dist=0
take 1 dist=0
take 1 dist=0
0 4 1 -1 -1 -1

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

แบบที่ 2 ใช้ int กับ INT_MAX และไม่หยุดเมื่อไปไม่ถึง

หลายคนใช้ INT_MAX แทนอนันต์ เพราะจำง่าย แล้วตัดบรรทัด if (dist[u] == INF) break; ทิ้งเพราะคิดว่าไม่จำเป็น แผนที่ชุดนี้มีหมู่บ้าน 4 5 6 ที่ไม่มีถนนเชื่อมกับบ้าน

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

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});
        adj[v].push_back({u, w});
    }
    vector<int> dist(n + 1, INT_MAX);
    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;
            }
        }
        done[u] = true;
        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;
}

0 3 1 -2147483635 -2147483642 -2147483639

สามจุดที่ไปไม่ถึงได้ระยะติดลบ เมื่อจุด 1 2 3 เสร็จหมด จุดที่เหลือมี dist เป็น INT_MAX ทุกจุด โปรแกรมเลือกจุด 4 แล้วผ่อนถนนไปจุด 5 ได้ INT_MAX + 7 ซึ่งล้นเป็นค่าติดลบตามหน้า 1.3 และน้อยกว่า INT_MAX จึงถูกเก็บ ค่าติดลบนั้นยังลามต่อไปจุด 6 และย้อนกลับมาจุด 4 อีก แก้ได้สองทางพร้อมกัน คือหยุดเมื่อจุดที่น้อยที่สุดเป็นอนันต์ และใช้ long long กับอนันต์ที่บวกแล้วไม่ล้น เช่น 10¹⁸ แบบโปรแกรมต้นฉบับ

สรุป

ในกราฟมีน้ำหนัก ความยาวเส้นทางคือผลรวมน้ำหนัก BFS ให้ทางที่ผ่านน้อยเส้นที่สุด ซึ่งไม่ใช่ทางที่สั้นที่สุด
เก็บกราฟด้วย vector<vector<pair<int, int>>> แต่ละช่องคือ (ปลายทาง, น้ำหนัก)
ผ่อนระยะ ถ้า dist[u] + w < dist[v] ให้แก้ dist[v] ทุกวิธีในบทนี้ต่างกันแค่ลำดับของการผ่อน
Dijkstra เลือกจุดที่ยังไม่เสร็จที่ใกล้ที่สุด ประกาศว่าเสร็จ แล้วผ่อนถนนที่ออกจากจุดนั้น ถูกต้องเมื่อน้ำหนักไม่ติดลบ
แบบอาเรย์เป็น O(V² + E) ใช้ long long และอนันต์ 10¹⁸ หยุดเมื่อจุดที่น้อยที่สุดไปไม่ถึง