Graph AlgosGraph Algorithms

Bellman-Ford

Single-source shortest paths that tolerate negative edge weights: relax every edge V - 1 times, then one more pass to detect negative cycles.

Learn Bellman-Ford →

Weighted graph — One edge per line: "A B 4". Optional "source: A" / "target: F" lines.

Distances per round

round	S	A	B	C	D	E
0	0	∞	∞	∞	∞	∞
now	0	∞	∞	∞	∞	∞

1/21dist[S] = 0, all others ∞. Bellman-Ford relaxes every edge up to n-1 = 5 times: after round i every shortest path using ≤ i edges is correct, so 5 rounds cover any simple path.

Edge being checkedEdge that improved a distance this roundCurrent parent edgeFinal shortest pathEdge proving a negative cycle

PseudocodeLearn Bellman-Ford →

1dist = {v: ∞}; dist[source] = 0
2for round in 1 .. n-1:
3  for (u, v, w) in edges:
4    if dist[u] + w < dist[v]:
5      dist[v] = dist[u] + w; parent[v] = u
6  if nothing changed: break
7for (u, v, w) in edges:
8  if dist[u] + w < dist[v]: report negative cycle

Complexity

best O(E)

avg O(V · E)

worst O(V · E)

space O(V)

Speed