Dijkstra

Pada GPS navigation, protokol routing OSPF, dan pathfinding game, satu algoritma mendominasi: Dijkstra. Diterbitkan Edsger W. Dijkstra pada 1959, algoritma ini mencari jalur terpendek dari satu node sumber ke semua node lain pada graph berbobot non-negatif. Strateginya adalah greedy: setiap langkah, pilih node belum diproses dengan jarak terkecil, lalu relaksasi semua edge keluarnya. Dengan priority queue, kompleksitasnya O((V + E) log V) — efisien untuk graph dengan jutaan edge. Pada Chapter ini kita akan membedah mekanisme greedy Dijkstra, mengimplementasikannya dengan std::priority_queue, dan menelusuri kenapa algoritma ini gagal pada bobot negatif.

Aturan: Greedy Pilih Jarak Terkecil #

Diberikan graph berbobot non-negatif dan node sumber src, Dijkstra menyimpan array dist[] berisi estimasi jarak terkecil sementara. Inisialisasi: dist[src] = 0, sisanya INF. Setiap langkah:

1. Pilih node u belum diproses dengan dist[u] terkecil.
2. Tandai u selesai — dist[u] adalah jarak final.
3. Untuk setiap edge (u, v, w): bila dist[u] + w < dist[v], perbarui dist[v].

Loop berhenti saat semua node diproses atau queue kosong.

Mekanisme: Priority Queue + Lazy Deletion #

Pilihan node dengan dist terkecil pada setiap iterasi mengingatkan pada min-heap. std::priority_queue default adalah max-heap — gunakan std::greater<std::pair<long long,int>> untuk mendapatkan min-heap.

Trik lazy deletion: ketika dist[v] diperbarui, kita tidak menghapus entri lama (dist_lama, v) dari heap (karena std::priority_queue tidak mendukung operasi ini). Sebagai gantinya, kita push entri baru (dist_baru, v) dan saat entri lama muncul di top, kita cek apakah dist[u] di array sudah lebih kecil dari d di heap — bila ya, entri tersebut sudah kedaluwarsa, skip.

Implementasi dengan std::priority_queue #

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>

const long long INF = LLONG_MAX / 4;

std::vector<long long> dijkstra(int n,
        const std::vector<std::vector<std::pair<int,int>>>& adj, int src) {
    std::vector<long long> dist(n, INF);
    std::vector<bool> done(n, false);
    // min-heap: (dist, node)
    using P = std::pair<long long,int>;
    std::priority_queue<P, std::vector<P>, std::greater<P>> pq;

    dist[src] = 0;
    pq.push({0, src});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (done[u]) continue;        // lazy deletion
        done[u] = true;
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

int main() {
    // Graph:
    //   0 -(4)-> 1 -(1)-> 2
    //   |        |       |
    //  (1)      (5)     (3)
    //   v        v       v
    //   3 -(2)-> 4 <-(2)- 2 (sama: 2->4)
    int n = 5;
    std::vector<std::vector<std::pair<int,int>>> adj(n);
    auto add = [&](int u, int v, int w) { adj[u].push_back({v, w}); };
    add(0, 1, 4); add(0, 3, 1);
    add(1, 2, 1); add(1, 4, 5);
    add(2, 4, 2);
    add(3, 4, 2);

    auto dist = dijkstra(n, adj, 0);
    std::cout << "Dijkstra dari node 0:\n";
    for (int i = 0; i < n; ++i) {
        std::cout << "  dist[" << i << "] = " << dist[i] << '\n';
    }

    std::cout << "\nTrace jarak akhir:\n";
    std::cout << "  0 -> 1 : 4 (langsung)\n";
    std::cout << "  0 -> 2 : 5 (0->1->2)\n";
    std::cout << "  0 -> 3 : 1 (langsung)\n";
    std::cout << "  0 -> 4 : 3 (0->3->4)\n";
    return 0;
}

Output yang Dihasilkan:

Dijkstra dari node 0:
  dist[0] = 0
  dist[1] = 4
  dist[2] = 5
  dist[3] = 1
  dist[4] = 3

Trace jarak akhir:
  0 -> 1 : 4 (langsung)
  0 -> 2 : 5 (0->1->2)
  0 -> 3 : 1 (langsung)
  0 -> 4 : 3 (0->3->4)

Bedah Kode Baris-per-Baris #

1. std::vector<long long> dist(n, INF): gunakan long long untuk menghindari overflow saat dist[u] + w melebihi INT_MAX. INF = LLONG_MAX / 4 memberi margin aman.
2. std::vector<bool> done(n, false): penanda node yang sudah final — jaraknya tidak akan diupdate lagi. Inilah inti invariant greedy Dijkstra.
3. std::priority_queue<P, std::vector<P>, std::greater<P>> pq: min-heap berisi (distance, node). std::greater membalik urutan default (max-heap) menjadi min-heap.
4. pq.push({0, src}): inisialisasi. Sumber berjarak 0, push ke heap.
5. auto [d, u] = pq.top(); pq.pop();: ambil pasangan (distance, node) dengan distance terkecil. Structured binding C++17 mempermudah dekomposisi.
6. if (done[u]) continue: lazy deletion. Bila u sudah diproses sebelumnya, ini adalah entri kedaluwarsa di heap — skip tanpa memproses ulang. Tanpa skip ini, kompleksitas bisa menjadi O(E²) pada kasus buruk.
7. done[u] = true: tandai u final. Setelah baris ini, dist[u] tidak akan diupdate lagi — inilah jarak terpendek sebenarnya dari src ke u.
8. for (auto [v, w] : adj[u]): iterasi edge keluar u. Setiap edge diperiksa satu kali saat u di-finalize.
9. if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pq.push({dist[v], v}); }: relaksasi edge. Bila ditemukan jarak lebih kecil, update dist[v] dan push ke heap. Push baru — tidak menghapus entri lama untuk v.
10. dist[4] = 3 bukan 5: path 0 → 3 → 4 (1+2=3) lebih pendek dari 0 → 1 → 4 (4+5=9) atau 0 → 1 → 2 → 4 (4+1+2=7). Dijkstra memilih 3 karena saat memproses node 3 (dist=1), dist[4] diperbarui dari 9 menjadi 3.

Trace Step-by-Step #

Tanda * = entri kedaluwarsa yang di-skip via lazy deletion.

Kompleksitas #

Variasi #

• Early termination: bila hanya butuh jarak ke satu tujuan dst, hentikan loop saat u == dst. Menghemat waktu rata-rata, namun worst case tetap O((V + E) log V).
• A* search: tambahkan heuristik h(v) (estimasi jarak ke tujuan). Skor = g(v) + h(v) di mana g(v) = jarak tempuh dari src. Optimal bila h admissible (tidak overestimate).
• Bidirectional Dijkstra: jalankan Dijkstra dari src dan dst (pada graph reversed) secara bersamaan, berhenti saat frontier bertemu. Kompleksitas turun secara praktis.
• Multi-source Dijkstra: push beberapa sumber ke heap sekaligus dengan dist=0. Berguna untuk “jarak ke pomp terdekat”.

Aplikasi Nyata #

• OSPF routing: protokol interior gateway menggunakan Dijkstra untuk membangun routing table.
• GPS navigation: Google Maps dan sejenisnya menggunakan varian A* (Dijkstra + heuristik geografis) untuk routing real-time.
• Network path analysis: mencari jalur dengan latency minimum antar server.
• Pathfinding di game: A* atau Dijkstra untuk navigasi NPC pada grid map.
• Social network analysis: jarak terpendek antar user = kekuatan koneksi.

Ringkasan #

• Dijkstra menyelesaikan SSSP pada graph berbobot non-negatif dengan strategi greedy.
• Implementasi dengan std::priority_queue + lazy deletion memberi O((V + E) log V).
• Tandai done[u] saat di-pop untuk mencegah pemrosesan ulang.
• Tidak menangani bobot negatif — gunakan Bellman-Ford.
• Variasi: early termination, A* (heuristik), bidirectional, multi-source.

Bab berikutnya akan membahas Bellman-Ford — algoritma yang lebih lambat namun mampu menangani bobot negatif dan mendeteksi siklus berbobot negatif.