מוטיבציה

האלגוריתם Bellman-Ford מבוסס על פעולה אחת, הרפיה: עבור קשת u -> v במשקל w, אם המעבר דרך u זול יותר (dist[u] + w < dist[v]), מעדכנים את dist[v]. עושים זאת עבור כל קשת, שוב ושוב.

למה ללמוד את Bellman-Ford?

• משקלים שליליים: הוא פועל במקרים שבהם Dijkstra לא יכול, למשל כשמדובר בעלויות שיכולות לכלול החזרים או ארביטראז׳ במטבעות.
• זיהוי מחזורים שליליים: מעבר הרפיה נוסף חושף מחזורים שסכום המשקלים שלהם שלילי.
• פשטות: אין תור עדיפויות, רק הרפיה חוזרת של קשתות.

המחיר הוא מהירות: O(V * E), איטי יותר מ־O((V + E) log V) של Dijkstra.