Bellman-Ford & Sisi Negatif

Dijkstra menganggap jarak yang diambil sudah final, tetapi sisi negatif dapat membuat sebuah jalur menjadi lebih murah di kemudian waktu. Karena itu, Dijkstra gagal pada kasus tersebut.

Bellman-Ford menangani bobot sisi negatif. Algoritme ini lebih lambat daripada Dijkstra, tetapi andal ketika logika serakah tidak dapat dipercaya.

Algoritme ini berulang kali merelaksasikan setiap sisi: jika dist[u] ditambah bobot sisi lebih kecil daripada dist[v], perbarui dist[v] menjadi nilai yang lebih kecil tersebut.

Jalur terpendek menggunakan paling banyak V dikurangi 1 sisi, sehingga V-1 putaran relaksasi pada setiap sisi sudah cukup untuk menetapkan semua jarak.

Mulai dengan setiap jarak bernilai tak hingga, kecuali sumber yang bernilai nol, sama seperti pada Dijkstra.

Setiap putaran menelusuri seluruh daftar sisi sekali dan merelaksasikan setiap sisi. Perbaikan merambat ke luar sejauh satu lompatan pada setiap putaran.

Setelah k putaran, semua jalur terpendek yang menggunakan k sisi sudah benar. Setelah V-1 putaran, setiap jalur terpendek sederhana telah selesai diproses.

Jalankan satu putaran lagi. Jika ada jarak yang masih berkurang, berarti ada sesuatu yang terus menjadi lebih murah, yang menandakan adanya siklus negatif.

Siklus negatif berarti tidak ada jalur terpendek berhingga, karena Anda dapat terus berputar untuk menurunkan biaya tanpa batas.

Anda merelaksasikan E sisi selama V putaran, sehingga Bellman-Ford berjalan dalam O(V * E), yang sesuai untuk graf kecil atau menengah.

Pilih Dijkstra untuk bobot nonnegatif dan kecepatan. Pilih Bellman-Ford ketika bobot negatif muncul atau Anda harus mendeteksi siklus bermasalah.

Setelah V-1 putaran, sebuah jarak masih berkurang pada satu putaran lagi. Apa artinya?

Relaksasikan semua sisi selama V-1 putaran, lalu lakukan satu putaran lagi untuk mendeteksi siklus negatif. Algoritme ini berjalan dalam O(V*E), tetapi dapat bekerja pada kasus yang tidak dapat ditangani Dijkstra. ✅