Bellman-Ford Algorithm

overview

Summary

Bellman-Ford finds single-source shortest paths in weighted directed graphs, including those with negative edge weights. It reliably detects reachable negative cycles, which makes it more general than Dijkstra. The algorithm relaxes all edges up to V-1 times, then checks once more to flag negative cycles. It runs in O(VE) time and is practical for small to medium graphs or when negative weights are present.