Shortest Path

Graph berbobot adalah model alami untuk banyak persoalan nyata: jarak antar kota, biaya transit paket data, durasi penerbangan, harga tiket antar stasiun. Dalam semua kasus, satu pertanyaan inti muncul: bagaimana menemukan jalur dengan total bobot minimum? Tidak ada satu algoritma universal — pilihan algoritma bergantung pada apakah bobot bisa negatif, apakah kita butuh jarak dari satu sumber atau dari semua pasangan, dan apakah graph adalah DAG. Pada Chapter ini kita akan memetakan lima algoritma shortest path utama, melihat kapan masing-masing tepat, dan mengimplementasikan satu pendekatan khusus yang sering terlupakan: DAG shortest path berbasis topological sort.

Aturan: Variasi Persoalan Shortest Path #

Persoalan	Deskripsi
Single-source (SSSP)	Jarak dari satu sumber `src` ke semua node lain.
Single-destination	Jarak dari semua node ke satu tujuan — reduksi: balik arah edge, jalankan SSSP.
All-pairs (APSP)	Jarak antara setiap pasangan node — biasanya Floyd-Warshall.
Single-pair	Jarak satu sumber ke satu tujuan — algoritma SSSP berhenti early saat tujuan ter-extract.

Mekanisme: Memilih Algoritma yang Tepat #

flowchart TD A{"Graph punya bobot negatif?"} -- Ya --> B{"Punya siklus berbobot negatif?"} A -- Tidak --> C{"Butuh all-pairs?"} B -- Ya --> D["Tidak ada solusi (jarak = -∞)"] B -- Tidak --> E["Bellman-Ford O(V·E)"] C -- Ya --> F["Floyd-Warshall O(V³)"] C -- Tidak --> G{"Graph adalah DAG?"} G -- Ya --> H["DAG topo + relax O(V+E)"] G -- Tidak --> I["Dijkstra O((V+E) log V)"]

Lima algoritma utama dan kompleksitasnya:

Algoritma	Tipe	Kompleksitas	Bobot Negatif	Catatan
BFS	SSSP	`O(V + E)`	Tidak (dianggap 1)	Graph tak berbobot.
DAG shortest path	SSSP	`O(V + E)`	Boleh (tanpa siklus)	Topological order + relax.
Dijkstra	SSSP	`O((V + E) log V)`	Tidak	Greedy + priority queue.
Bellman-Ford	SSSP	`O(V · E)`	Ya, deteksi siklus negatif	Robust tapi lambat.
Floyd-Warshall	APSP	`O(V³)`	Ya, deteksi siklus negatif	DP over intermediate vertex.

Implementasi: DAG Shortest Path #

Pada DAG, urutan topologis memberikan kepastian: ketika memproses node u, semua prasyarat u sudah diproses. Maka kita bisa relaksasi edge dalam urutan topologis sekali lewat — tanpa priority queue, tanpa iterasi V-1 seperti Bellman-Ford.

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

const long long INF = LLONG_MAX / 4;

std::vector<long long> dag_shortest(const std::vector<std::vector<std::pair<int,int>>>& adj,
                                   int src) {
    int n = (int)adj.size();
    std::vector<int> indeg(n, 0);
    for (int u = 0; u < n; ++u)
        for (auto& [v, w] : adj[u]) indeg[v]++;

    std::queue<int> q;
    for (int u = 0; u < n; ++u) if (indeg[u] == 0) q.push(u);

    std::vector<int> topo;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        topo.push_back(u);
        for (auto& [v, w] : adj[u])
            if (--indeg[v] == 0) q.push(v);
    }

    std::vector<long long> dist(n, INF);
    dist[src] = 0;
    for (int u : topo) {
        if (dist[u] == INF) continue;
        for (auto& [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
        }
    }
    return dist;
}

int main() {
    // DAG: 5 node, edge berbobot
    //   0 -(2)-> 1 -(3)-> 2
    //   0 -(6)-> 2
    //   1 -(1)-> 3
    //   2 -(1)-> 3
    //   3 -(4)-> 4
    std::vector<std::vector<std::pair<int,int>>> adj(5);
    auto add = [&](int u, int v, int w) { adj[u].push_back({v, w}); };
    add(0, 1, 2);
    add(0, 2, 6);
    add(1, 2, 3);
    add(1, 3, 1);
    add(2, 3, 1);
    add(3, 4, 4);

    auto dist = dag_shortest(adj, 0);
    std::cout << "DAG shortest path dari 0:\n";
    for (int i = 0; i < 5; ++i) {
        if (dist[i] == INF) std::cout << "  ke " << i << ": unreachable\n";
        else std::cout << "  ke " << i << ": " << dist[i] << '\n';
    }

    std::cout << "\nPath 0->4: 0->1->3->4 = 2+1+4 = 7\n";
    std::cout << "Alternatif : 0->1->2->3->4 = 2+3+1+4 = 10 (lebih panjang)\n";
    return 0;
}

Output yang Dihasilkan:

text
DAG shortest path dari 0:
  ke 0: 0
  ke 1: 2
  ke 2: 5
  ke 3: 3
  ke 4: 7

Path 0->4: 0->1->3->4 = 2+1+4 = 7
Alternatif : 0->1->2->3->4 = 2+3+1+4 = 10 (lebih panjang)

Bedah Kode Baris-per-Baris #

for (auto& [v, w] : adj[u]) indeg[v]++: hitung in-degree setiap node. Adjacency list menyimpan pasangan (tetangga, bobot) — structured binding C++17 mempermudah akses.
Topological sort via Kahn: identik dengan implementasi pada Chapter topological sorting. Hasil topo menjamin prasyarat sudah diproses sebelum dependen.
std::vector<long long> dist(n, INF): gunakan long long untuk antisipasi overflow. INF dipilih LLONG_MAX / 4 agar penjumlahan dist[u] + w tidak overflow bahkan bila dist[u] belum diperbarui.
dist[src] = 0; for (int u : topo): relaksasi edge dalam urutan topologis. Untuk setiap u, periksa semua edge (u, v, w) dan perbarui dist[v] bila dist[u] + w < dist[v].
if (dist[u] == INF) continue: node u tak terjangkau dari src — skip, agar tidak menambah INF ke tetangganya.
Path terpendek 0 → 4: lewat 0 → 1 → 3 → 4 (bobot 2+1+4=7). Alternatif 0 → 1 → 2 → 3 → 4 (2+3+1+4=10) lebih panjang. DAG shortest path memilih otomatis berkat urutan topologis + relaksasi.
Kenapa ke 2 = 5 bukan 6? Path 0 → 1 → 2 (bobot 2+3=5) lebih kecil dari edge langsung 0 → 2 (bobot 6). Saat memproses node 1, dist[2] diperbarui dari 6 menjadi 5.

Kompleksitas DAG Shortest Path #

Aspek	Nilai
Waktu	`O(V + E)` (Kahn + satu kali relax)
Ruang	`O(V)`
Bobot negatif	Boleh, karena tanpa siklus tidak ada masalah.
Deteksi siklus negatif	Otomatis — siklus = bukan DAG.

Kapan Memilih Algoritma Mana #

Graph tak berbobot: BFS — paling cepat O(V + E), implementasi paling sederhana.
DAG berbobot (positif/negatif): DAG shortest path — O(V + E), tercepat untuk DAG.
Graph berbobot positif: Dijkstra — O((V + E) log V), standar industri.
Graph dengan bobot negatif (mungkin siklus negatif): Bellman-Ford — O(V · E), mendeteksi siklus negatif.
Butuh jarak semua pasangan: Floyd-Warshall — O(V³), sederhana dan kuat untuk V kecil (≤ 500).
Dense graph + all pairs: Johnson’s algorithm (Dijkstra + Bellman-Ford reweighting) — O(V² log V + V·E), lebih cepat dari Floyd-Warshall pada graph sparse.

Aplikasi Nyata #

Routing protokol (OSPF, IS-IS): Dijkstra untuk mencari jalur terpendek pada network graph.
GPS navigation: Dijkstra atau A* (heuristik) untuk navigasi real-time.
Currency arbitrage: deteksi peluang arbitrage = cari siklus negatif pada graph konversi mata uang → Bellman-Ford.
Project scheduling (CPM/PERT): longest path pada DAG = critical path yang menentukan durasi total proyek. Negasi bobot, jalankan DAG shortest path.
Network latency analysis: all-pairs shortest path untuk memahami worst-case latency.

Ringkasan #

Lima algoritma utama: BFS, DAG shortest path, Dijkstra, Bellman-Ford, Floyd-Warshall.
Pilihan algoritma bergantung pada: bobot negatif, all-pairs vs single-source, dan apakah graph adalah DAG.
DAG shortest path: topological sort + satu kali relaksasi, O(V + E), tercepat untuk DAG.
Dijkstra: standar untuk bobot positif, O((V + E) log V).
Bellman-Ford: untuk bobot negatif, O(V · E).
Floyd-Warshall: all-pairs, O(V³), sederhana untuk V kecil.

Empat bab berikutnya akan membedah masing-masing algoritma secara mendalam — Dijkstra, Bellman-Ford, Floyd-Warshall — dengan implementasi C++ lengkap dan trace langkah demi langkah.