Motivasi

Bellman-Ford dibangun berdasarkan satu operasi, relaksasi: untuk sebuah edge u -> v dengan bobot w, jika melewati u lebih murah (dist[u] + w < dist[v]), perbarui dist[v]. Lakukan itu untuk setiap edge, berulang kali.

Mengapa mempelajari Bellman-Ford?

• Bobot negatif: algoritma ini berfungsi saat Dijkstra tidak bisa, misalnya untuk biaya yang bisa berupa rabat atau arbitrase mata uang.
• Deteksi siklus negatif: satu kali lintasan relaksasi tambahan mengungkap siklus yang total bobotnya negatif.
• Kesederhanaan: tanpa priority queue, cukup relaksasi edge berulang kali.

Komprominya adalah kecepatan: O(V * E), lebih lambat daripada O((V + E) log V) milik Dijkstra.