Page 30 • Dynamic Programming / Graph

Bellman-Ford Algorithm

Single-source shortest path using V−1 relaxation rounds, followed by negative cycle detection. Works with negative edge weights.

Interactive Graph Dry Run

Click “Start” to initialize distances.

Negative cycle: not checked

current edgerelaxed edge / updated nodenegative-cycle evidencenormal edge

Concept

For every edge u → v with weight w, Bellman-Ford checks:

if dist[u] + w < dist[v], then dist[v] = dist[u] + w

Source Vertex

Vertex	Distance	Parent

Step Log

Ready.

Algorithm Steps

Initialize source distance as 0 and all other distances as ∞.
Repeat edge relaxation exactly V−1 times.
Run one extra pass over all edges.
If any distance still improves, a negative weight cycle exists.

Complexity

Time complexity: O(VE)
Space complexity: O(V)
Useful when negative edge weights are present, unlike Dijkstra’s basic form.

Pseudocode

BellmanFord(G, source): for each vertex v: dist[v] = ∞ parent[v] = NIL dist[source] = 0 for i = 1 to |V| - 1: for each edge (u, v, w): if dist[u] + w < dist[v]: dist[v] = dist[u] + w parent[v] = u for each edge (u, v, w): if dist[u] + w < dist[v]: report "negative weight cycle exists"