Penjelasan algoritma Bellman-Ford: cara kerja, kode, dan kompleksitas

Masalah yang diselesaikan Bellman-Ford

Algoritma Dijkstra cepat tetapi mensyaratkan bobot edge non-negatif. Sebagian masalah memang punya bobot negatif: pengembalian dana, keuntungan dalam penukaran mata uang, atau biaya energi yang bisa turun di bawah nol. Bellman-Ford menangani graf seperti ini dengan benar dan juga memberi tahu bila jalur terpendek tidak ada karena siklus negatif, yaitu putaran yang bisa dilalui terus-menerus agar biaya makin kecil.

Algoritma ini dinamai dari Richard Bellman dan Lester Ford Jr., yang menerbitkan versinya pada tahun 1950-an.

Ide dasar dengan kata-kata sederhana

1. Atur jarak node awal menjadi 0 dan jarak lainnya menjadi tak hingga.
2. Ulangi V − 1 kali: untuk setiap edge u → v dengan bobot w, jika dist[u] + w < dist[v], perbarui dist[v].
3. Lakukan satu putaran lagi pada semua edge. Jika masih ada jarak yang membaik, laporkan siklus negatif.

Mengapa V − 1 putaran? Jalur terpendek tanpa siklus memakai paling banyak V − 1 edge. Setelah putaran ke-k, setiap node yang jalur terpendeknya paling banyak k edge sudah memiliki jarak yang benar, sehingga V − 1 putaran mencakup semua jalur sederhana.

Contoh langkah demi langkah

Graf berarah dengan 4 node dan edge S→A (4), S→B (5), B→A (−3), A→C (3). Edge diproses dalam urutan ini di setiap putaran.

Pada putaran 1, A mula-mula menjadi 4 lewat S→A, lalu membaik menjadi 2 lewat B→A, dan C memakai nilai yang sudah membaik. Algoritma Dijkstra akan memfinalisasi A pada 4 sebelum melihat B, yang persis merupakan kesalahan akibat edge negatif.

Implementasi Python

Bellman-Ford bekerja pada list edge biasa, sehingga penulisannya singkat:

def bellman_ford(nodes, edges, start):
    """edges: list of (u, v, weight). Returns dist, or raises on a negative cycle."""
    INF = float("inf")
    dist = {n: INF for n in nodes}
    dist[start] = 0
    for _ in range(len(nodes) - 1):
        changed = False
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:
            break                         # already optimal
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            raise ValueError("graph contains a negative cycle")
    return dist
nodes = ["S", "A", "B", "C"]
edges = [("S", "A", 4), ("S", "B", 5), ("B", "A", -3), ("A", "C", 3)]
print(bellman_ford(nodes, edges, "S"))  # {'S': 0, 'A': 2, 'B': 5, 'C': 5}

Menambahkan edge C → B dengan bobot −6 membentuk siklus B → A → C → B dengan total bobot −3 + 3 − 6 = −6, sehingga putaran tambahan menemukannya:

try:
    bellman_ford(nodes, edges + [("C", "B", -6)], "S")
except ValueError as e:
    print(e)  # graph contains a negative cycle

Pemeriksaan dist[u] != INF melewati edge yang keluar dari node yang belum dijangkau. Di Python, float("inf") + w tetap tak hingga, jadi pemeriksaan ini terutama menghemat kerja. Pada bahasa yang memakai bilangan bulat besar sebagai tak hingga, pemeriksaan ini mencegah overflow dan pembaruan palsu.

Kompleksitas waktu dan ruang

Pada graf dengan 1.000 node dan 10.000 edge, itu bisa mencapai sekitar 10 juta relaksasi, sehingga Dijkstra jauh lebih cepat bila semua bobot non-negatif.

Varian dan kesalahan umum

• Keluar lebih awal: berhenti saat satu putaran penuh tidak mengubah apa pun. Ini aman dan sering membuat algoritma jauh lebih cepat dalam praktik.
• SPFA (shortest path faster algorithm): hanya merelaksasi ulang edge dari node yang jaraknya berubah, memakai queue. Biasanya cepat tetapi kasus terburuknya tetap O(V × E).
• Jalur dengan batas hop: menjalankan tepat k putaran, dengan salinan jarak dari putaran sebelumnya, menghasilkan jalur termurah dengan paling banyak k edge. Ini menyelesaikan soal "cheapest flights within k stops".
• Menemukan siklusnya: simpan peta parent; saat putaran tambahan memperbarui node v, ikuti parent sebanyak V kali untuk masuk ke dalam siklus, lalu telusuri sampai kembali ke node yang sama.

Kapan memakainya dan penggunaannya di dunia nyata

• Gunakan Bellman-Ford jika bobot edge bisa negatif atau jika Anda harus mendeteksi siklus negatif. Selain itu, pilih Dijkstra.
• Protokol routing distance-vector, seperti RIP, memakai gagasan Bellman-Ford terdistribusi: setiap router terus memperbarui estimasi jaraknya dari estimasi tetangganya.
• Arbitrase mata uang: dengan bobot -log(rate), siklus negatif adalah rangkaian penukaran yang berakhir dengan uang lebih banyak daripada awalnya.
• Algoritma Johnson menjalankan Bellman-Ford sekali untuk memberi bobot ulang pada graf sehingga Dijkstra bisa dipakai dari setiap node untuk jalur terpendek semua pasangan.
• Difference constraints (sistem pertidaksamaan seperti x - y <= c) dapat diselesaikan sebagai jalur terpendek; siklus negatif berarti tidak ada solusi.