Động lực

Bellman-Ford dựa trên một thao tác, nới lỏng: với một cạnh u -> v có trọng số w, nếu đi qua u tốn ít hơn (dist[u] + w < dist[v]), hãy cập nhật dist[v]. Lặp lại thao tác đó với mọi cạnh.

Vì sao nên học Bellman-Ford?

• Trọng số âm: thuật toán này hoạt động trong những trường hợp Dijkstra không thể xử lý, chẳng hạn như chi phí có thể được giảm giá hoặc có thể thực hiện kinh doanh chênh lệch tỷ giá.
• Phát hiện chu trình âm: thêm một lượt nới lỏng sẽ phát hiện các chu trình có tổng trọng số âm.
• Đơn giản: không cần hàng đợi ưu tiên, chỉ cần liên tục nới lỏng các cạnh.

Đổi lại là tốc độ: O(V * E), chậm hơn Dijkstra với độ phức tạp O((V + E) log V).