Bellman–Ford Algorithm
A single-source shortest path algorithm that handles negative edge weights and detects negative cycles, running in O(V×E) time.
.png)
The Bellman–Ford algorithm computes shortest paths from a single source vertex to every other vertex in a weighted directed graph, and unlike Dijkstra's algorithm it works correctly when some edge weights are negative. It was developed independently by Richard Bellman and Lester Ford Jr. in the 1950s. The algorithm is a direct application of dynamic programming: it builds the shortest-path distances pass by pass, exploiting the fact that any shortest path uses at most V−1 edges in a graph with V vertices.
The algorithm initializes the source distance to zero and all others to infinity, then repeatedly relaxes every edge: if dist[u] + w(u,v) is smaller than the current dist[v], the distance to v is lowered. After V−1 full passes over all edges, every shortest path has been found, because a shortest path can never repeat a vertex and therefore contains at most V−1 edges. The final pass is a diagnostic: if any edge can still be relaxed, the graph contains a negative cycle reachable from the source, and no finite shortest path exists.
function bellman_ford(graph, source):
dist[source] = 0
for each vertex v != source: dist[v] = infinity
for i = 1 to V - 1:
for each edge (u, v, weight):
if dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
for each edge (u, v, weight):
if dist[u] + weight < dist[v]:
error "negative cycle reachable from source"
return dist
With V vertices and E edges the running time is O(V×E), which is slower than Dijkstra's O((V+E) log V) — the price paid for supporting negative weights — so in practice Dijkstra is preferred on non-negative graphs and Bellman–Ford on graphs where negatives appear. The Big O contrast between the two is a standard teaching example. Bellman–Ford also detects negative cycles, which makes it useful outside routing: currency arbitrage is modeled as finding a negative cycle in a graph whose edge weights are logarithms of exchange rates, and systems of difference constraints (used in scheduling and real-time analysis) are solved by converting them to shortest-path problems and running Bellman–Ford.
Tags
algorithms dynamic programming graph theory shortest path