Bellman-Ford

Single-source shortest path algorithm that handles negative edge weights.

Step 1 of 15

Initialise. Distance to "A" = 0; all others = ∞.

Pass

Initialising…

Distances from A

A	0
B	∞
C	∞
D	∞
E	∞

▶Algorithm

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

Legend

Edge being checked

Distance updated

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

1 / 15Speed