Learn
Bellman-Ford Algorithm
The Bellman-Ford Algorithm finds shortest paths from a source vertex while handling negative edge weights. Unlike Dijkstra, it can also detect negative cycles in the graph.
You relax all edges times. After iterations, you've found all shortest paths if no negative cycle exists.
function bellmanFord(edges, n, source):
dist = array of size n, initialized to infinity
dist[source] = 0
for i from 1 to n - 1:
for each edge (u, v, weight):
if dist[u] != infinity and dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
for each edge (u, v, weight):
if dist[u] != infinity and dist[u] + weight < dist[v]:
mark v as affected by negative cycle
return dist
Detecting negative cycles: After iterations, any edge that can still be relaxed indicates a negative cycle.
Why iterations: The longest simple path has at most edges. Each iteration guarantees correct distances for paths with one more edge.
Applications: You use Bellman-Ford for currency arbitrage detection, network routing with variable costs, and graphs with negative weights.
Time complexity: because you iterate times over all edges.
Space complexity: for the distance array.