Bellman-Ford

Dijkstra menggantung saat ada edge dengan bobot negatif: invariant greedy-nya rusak, hasil bisa salah tanpa peringatan. Sayangnya, banyak persoalan nyata memang punya bobot negatif — arbitrage mata uang, model biaya/profit, transfer dengan bonus. Bellman-Ford adalah algoritma SSSP yang robust: menerima bobot negatif, sekaligus mendeteksi siklus berbobot negatif yang membuat persoalan tidak punya solusi (jarak dapat di--∞). Harganya adalah kompleksitas O(V · E) — lebih lambat dari Dijkstra, namun kompromi yang sepadan untuk graph dengan bobot negatif. Pada Chapter ini kita akan membedah mekanisme relaksasi iteratifnya, mengimplementasikan dalam C++, dan melihat kenapa V-1 iterasi sudah cukup.

Aturan: Relax Semua Edge V-1 Kali #

Diberikan graph berarah berbobot (boleh negatif) dan node sumber src, Bellman-Ford mengulang proses berikut V-1 kali: untuk setiap edge (u, v, w), bila dist[u] + w < dist[v], perbarui dist[v]. Setelah V-1 iterasi, jarak terpendek sudah konvergen (kalau tidak ada siklus negatif).

Untuk deteksi siklus negatif: jalankan iterasi ke-V. Bila masih ada edge yang bisa merelaksasi → ada siklus berbobot negatif yang dapat mengurangi jarak tanpa batas.

Mekanisme: Relaxation Iteratif #

Relaksasi sebuah edge (u, v, w) berarti: periksa apakah dist[u] + w lebih kecil dari dist[v] yang saat ini tersimpan. Bila ya, update. Setiap iterasi relaksasi semua edge menyebarkan informasi jarak satu langkah lebih jauh dari sumber.

flowchart TD A["dist[src]=0, lainnya INF"] --> B["Iterasi i = 1..V-1"] B --> C["Untuk setiap edge u→v,w:<br/>if dist[u]+w < dist[v]:<br/>dist[v] = dist[u]+w"] C --> D{"Updated di iterasi ini?"} D -- Ya --> E["i < V-1?"] E -- Ya --> B E -- Tidak --> F["Iterasi V: cek siklus"] D -- Tidak --> F F --> G{"Ada edge yang masih<br/>bisa relax?"} G -- Ya --> H["Siklus berbobot negatif!"] G -- Tidak --> I["Selesai, dist valid"]

Implementasi Bellman-Ford #

cpp
#include <iostream>
#include <vector>
#include <tuple>
#include <climits>

const long long INF = LLONG_MAX / 4;

// Hasil: (sukses, dist). sukses=false bila ada siklus berbobot negatif.
std::pair<bool, std::vector<long long>>
bellman_ford(int n, const std::vector<std::tuple<int,int,int>>& edges, int src) {
    std::vector<long long> dist(n, INF);
    dist[src] = 0;

    // Relax semua edge V-1 kali
    for (int i = 1; i <= n - 1; ++i) {
        bool updated = false;
        for (auto [u, v, w] : edges) {
            if (dist[u] != INF && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                updated = true;
            }
        }
        if (!updated) break; // optimasi: berhenti awal bila tidak ada update
    }

    // Iterasi ke-V: cek siklus negatif
    for (auto [u, v, w] : edges) {
        if (dist[u] != INF && dist[u] + w < dist[v]) {
            return {false, {}}; // siklus berbobot negatif terdeteksi
        }
    }
    return {true, dist};
}

int main() {
    // Graph berarah dengan bobot negatif (tetapi tanpa siklus negatif):
    //   0 -(4)-> 1 -(-1)-> 2
    //   |        |        |
    //  (1)      (5)      (3)
    //   v        v        v
    //   3 -(2)-> 4 <---(-2)--- 2
    int n = 5;
    std::vector<std::tuple<int,int,int>> edges;
    auto add = [&](int u, int v, int w) { edges.push_back({u, 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 [ok, dist] = bellman_ford(n, edges, 0);
    std::cout << "Bellman-Ford dari node 0:\n";
    if (!ok) {
        std::cout << "  Terdeteksi siklus berbobot negatif!\n";
        return 0;
    }
    for (int i = 0; i < n; ++i) {
        std::cout << "  dist[" << i << "] = " << dist[i] << '\n';
    }

    std::cout << "\nTrace:\n";
    std::cout << "  0->3      : 1\n";
    std::cout << "  0->1      : 4\n";
    std::cout << "  0->1->2   : 4 + (-1) = 3\n";
    std::cout << "  0->1->2->4: 3 + (-2) = 1\n";

    // === Tes siklus negatif ===
    std::cout << "\n=== Tes siklus berbobot negatif ===\n";
    // 0 -> 1 (1), 1 -> 2 (-3), 2 -> 0 (1). Total: -1 (negatif!)
    int n2 = 3;
    std::vector<std::tuple<int,int,int>> cyc;
    cyc.push_back({0, 1, 1});
    cyc.push_back({1, 2, -3});
    cyc.push_back({2, 0, 1});

    auto [ok2, dist2] = bellman_ford(n2, cyc, 0);
    if (!ok2) std::cout << "  Siklus negatif terdeteksi (sesuai harapan).\n";
    else std::cout << "  Tidak ada siklus negatif.\n";
    return 0;
}

Output yang Dihasilkan:

text
Bellman-Ford dari node 0:
  dist[0] = 0
  dist[1] = 4
  dist[2] = 3
  dist[3] = 1
  dist[4] = 1

Trace:
  0->3      : 1
  0->1      : 4
  0->1->2   : 4 + (-1) = 3
  0->1->2->4: 3 + (-2) = 1

=== Tes siklus berbobot negatif ===
  Siklus negatif terdeteksi (sesuai harapan).

Bedah Kode Baris-per-Baris #

std::vector<std::tuple<int,int,int>> edges: list edge (u, v, w). Bellman-Ford tidak butuh adjacency list — list edge saja cukup, dan ini lebih efisien untuk relaksasi iteratif.
std::vector<long long> dist(n, INF): estimasi jarak. INF = LLONG_MAX / 4 menghindari overflow saat dist[u] + w walau dist[u] belum diperbarui.
for (int i = 1; i <= n - 1; ++i): iterasi V-1 kali. Pada iterasi i, jarak sepanjang i edge sudah benar (provability via induction).
if (dist[u] != INF && dist[u] + w < dist[v]): cek relaksasi. dist[u] != INF penting untuk tidak memulai dari INF + w yang bisa underflow atau overflow.
if (!updated) break;: optimasi. Bila suatu iterasi tidak ada update sama sekali, iterasi berikutnya juga tidak akan ada — algoritma sudah konvergen. Pada praktik, banyak graph konvergen dalam beberapa iterasi.
Iterasi ke-V untuk cek siklus: jalankan relaksasi sekali lagi. Bila masih ada update, berarti siklus berbobot negatif terdeteksi — jarak bisa dikurangi tanpa batas.
return {false, {}}: konvensi return — bool pertama menandakan sukses, vector kedua berisi dist bila sukses atau kosong bila gagal.
dist[4] = 1 bukan 9 atau 5: jalur terpendek adalah 0 → 1 → 2 → 4 (4 + (-1) + (-2) = 1), bukan 0 → 1 → 4 (4+5=9) atau 0 → 3 → 4 (1+2=3). Bobot negatif membuat jalur “memutar” menjadi lebih murah.
dist[2] = 3 bukan 6 (langsung): tidak ada edge langsung dari 0 ke 2. Bellman-Ford menemukan jalur via 0 → 1 → 2 (bobot 4 + (-1) = 3) yang lebih pendek dari estimasi awalnya.
Siklus negatif terdeteksi: graph kedua memiliki siklus 0 → 1 → 2 → 0 dengan total bobot 1 + (-3) + 1 = -1. Iterasi ke-3 (V=3, jadi V-1=2 iterasi relax, iterasi ke-V=3 untuk cek) mendeteksi masih ada update — return false.

Trace Iterasi (Graph Pertama) #

Iterasi	Edge yang relax	dist setelah iterasi
Init	—	`[0, ∞, ∞, ∞, ∞]`
1	`(0,1,4), (0,3,1)`	`[0, 4, ∞, 1, ∞]`
2	`(1,2,-1), (3,4,2)`	`[0, 4, 3, 1, 3]`
3	`(2,4,-2)`	`[0, 4, 3, 1, 1]`
4	(tidak ada update)	berhenti awal — konvergen
Cek (ke-V)	tidak ada update	tidak ada siklus negatif

Hanya 3 iterasi produktif (optimasi !updated), bukan V-1=4 — keunggulan praktis Bellman-Ford.

Kompleksitas #

Aspek	Nilai	Catatan
Waktu (worst)	`O(V · E)`	`V-1` iterasi × `E` edge per iterasi.
Waktu (praktis)	Sering lebih cepat	Optimasi `break` saat tidak ada update.
Ruang	`O(V + E)`	Array `dist` + list edge.
Bobot negatif	Ya	Mendukung semua bobot.
Deteksi siklus negatif	Ya	Iterasi ke-V.

Komparasi Dijkstra vs Bellman-Ford #

Aspek	Dijkstra	Bellman-Ford
Kompleksitas	`O((V + E) log V)`	`O(V · E)`
Bobot negatif	Tidak	Ya
Deteksi siklus negatif	Tidak	Ya
Implementasi	Min-heap + lazy deletion	Loop sederhana
Cocok untuk	Graph besar, bobot ≥ 0	Graph kecil-sedang, ada bobot negatif

Aplikasi Nyata #

Currency arbitrage detection: konversi rate(u, v) menjadi -log(rate) — siklus negatif = peluang arbitrage.
Network routing (RIP, BGP): protokol distance-vector yang merupakan varian Bellman-Ford terdistribusi.
Constraint satisfaction: teknik Bellman-Ford dipakai untuk menyelesaikan sistem constraint difference (x_j - x_i ≤ c).
Game AI: pathfinding pada map dengan efek slowdown (bobot negatif untuk bonus).

Ringkasan #

Bellman-Ford menyelesaikan SSSP dengan mendukung bobot negatif dan deteksi siklus negatif.
Strategi: relaksasi semua edge V-1 kali, lalu iterasi ke-V untuk deteksi.
Kompleksitas O(V · E) — lebih lambat dari Dijkstra, namun robust.
Optimasi break saat tidak ada update mempercepat konvergensi praktis.
Aplikasi: arbitrage, distance-vector routing, constraint satisfaction.

Bab berikutnya beralih ke persoalan all-pairs shortest path: Floyd-Warshall, algoritma DP yang elegan dengan kompleksitas O(V³).