Bellman-Ford
The Intuition
Bellman-Ford finds the shortest distance from one starting node to every other node. It works even when some edges have negative weights, which is the main reason to pick it over Dijkstra.
The plan is simple. Start with every distance set to "very large" except the starting node, which is 0. Then look at every edge in the graph and ask "if I take this edge, would the destination get a shorter total?". If yes, update the destination's distance. One pass over all edges is one round.
Repeat for V - 1 rounds, where V is the number of nodes. Why this many? Because the longest path in a graph with no repeats has at most V - 1 edges. After that many rounds, the shortest path to every reachable node has had enough chances to be discovered.
Negative cycles need special care. If a cycle has a total weight below zero, you can keep walking it forever and the distance keeps shrinking. There is no real shortest path. Bellman-Ford detects this with one extra round after the main loop. If any distance can still drop in this final round, a negative cycle exists somewhere reachable from the source. The standard convention is to mark all nodes reachable from such a cycle as "no shortest distance".
The cost is V * E because every round looks at every edge. That is slower than Dijkstra's (V + E) * log V. Use Bellman-Ford only when negative weights are possible. Use Dijkstra otherwise.
A real use case: arbitrage detection in currency conversion. Each currency is a node, each conversion rate is an edge with weight equal to the negative log of the rate. A path with negative total weight means a cycle of conversions that ends with more money than you started with. Bellman-Ford's negative-cycle detection is exactly the tool for this.
Shortest paths from one source when edges can have negative weights. Detecting negative cycles. Currency arbitrage. Any single-source shortest-path problem where Dijkstra is unsafe.
- All edge weights are non-negative (Dijkstra is faster)
- You need shortest paths between every pair of nodes (use Floyd-Warshall for small graphs)
- The graph is huge and dense and you need speed (look into Johnson's algorithm or specialized variants)
Variations:
- Early stop: If a round changes nothing, the result is final. Skip the remaining rounds.
- SPFA (Shortest Path Faster Algorithm): A queue-based version that often runs faster in practice but has the same worst case.
- Path reconstruction: Keep a parent pointer for each node. When a relaxation succeeds, record the previous node so you can rebuild the path at the end.
- a node not reachable from the source stays at infinity
- the source itself stays at 0
- a graph with no edges produces all infinities except the source
- a negative cycle that is not reachable from the source does not affect the result
Key Points
- •Use this when edge weights can be negative. Dijkstra cannot handle negative weights correctly.
- •The idea is to repeatedly look at every edge and ask "is there a shorter way to reach this neighbor?"
- •One full pass over all edges is called a "round". Repeat for V minus 1 rounds, where V is the number of nodes.
- •V minus 1 rounds is enough because the longest path with no repeats has at most V minus 1 edges.
- •One extra round at the end detects negative cycles. If any distance still drops, a cycle with negative total exists.
- •Slower than Dijkstra. Pick Bellman-Ford only when negative weights are actually possible.
Code Template
1 def bellman_ford(n, edges, source):
2 """
3 Shortest distance from source to every node.
4 n: number of nodes (0..n-1).
5 edges: list of (u, v, w) directed edges with possibly negative w.
6 Returns (distances, has_negative_cycle).
7 """
8 INF = float('inf')
9 dist = [INF] * n
10 dist[source] = 0
11
12 # Round 1 to round n-1: relax every edge.
13 for _ in range(n - 1):
14 changed = False
15 for u, v, w in edges:
16 if dist[u] != INF and dist[u] + w < dist[v]:
17 dist[v] = dist[u] + w
18 changed = True
19 # Optimization: stop if nothing improved this round.
20 if not changed:
21 break
22
23 # One more round. If any edge can still relax, a negative cycle exists.
24 for u, v, w in edges:
25 if dist[u] != INF and dist[u] + w < dist[v]:
26 return dist, True
27
28 return dist, FalseCommon Mistakes
- Stopping after V rounds instead of V minus 1 (doing one extra round means redoing work; the extra round is for cycle detection only)
- Forgetting to set the start node's distance to 0 (everything else stays at infinity)
- Updating from a stale copy of distances (in this implementation we do allow that; it just makes paths reach further per round)
- Reporting wrong distances when a negative cycle exists (any node reachable from the cycle has no real shortest distance)