📋 הנחות המוצא
גרף G=(V,E) עם n קודקודים ומשקלות. רצנו n−1 איטרציות של Bellman-Ford מ-s.
באיטרציה ה-n בודקים קשת (u, v) ומגלים ששיפור אפשרי:
באיטרציה ה-n בודקים קשת (u, v) ומגלים ששיפור אפשרי:
d[v] > d[u] + w(u, v)
טענה: עקיבה אחרי מצביעי אב החל מ-v לא תסתיים ב-null, ולכן קיים מעגל במצביעי האב.
אסטרטגיה: הוכחה בשלילה.
אסטרטגיה: הוכחה בשלילה.
⚠️ הנחת השלילה: העקיבה האחורה מ-v דרך מצביעי parent מסתיימת ב-null (כלומר אין מעגל)