בלמן־פורד

אלגוריתם מסלול קצר ביותר ממקור יחיד שמטפל במשקלי קשת שליליים.

שלב 1 מתוך 15

אתחול. המרחק ל־"A" = 0; כל השאר = ∞.

מעבר

מאתחל…

מרחקים מ־A

A	0
B	∞
C	∞
D	∞
E	∞

▶אלגוריתם

dist[s] = 0; dist[v] = ∞ for all v ≠ s
repeat |V|−1 times:
for each edge (u, v, w):
if dist[u] + w < dist[v]:
  dist[v] = dist[u] + w
  // no improvement
// early exit: no changes this pass
// check for negative-weight cycle
// done

מקרא

קשת נבדקת

מרחק עודכן

The edge C→B has weight −6, enabling a shorter path to B via C. Dijkstra cannot handle this; Bellman-Ford can.

1 / 15מהירות