Why it exists
Dijkstra's greedy approach fails on negative edges. Bellman-Ford scans all edges repeatedly to find shortcuts that negative weights might offer.
Loading...
Loading...
Loading Curriculum...
Loading Subject...
Loading Topic...
Loading Lesson...
Loading Lab...
The Bellman-Ford algorithm computes shortest paths from a single source vertex to all others. Unlike Dijkstra, it handles negative edge weights and detects negative cycles.
Dijkstra's greedy approach fails on negative edges. Bellman-Ford scans all edges repeatedly to find shortcuts that negative weights might offer.
For each edge (u, v), if the distance to u plus the weight to v is less than the current distance to v, we update it. We do this V-1 times.
If any distance can still be reduced after V-1 passes, the graph contains a negative loop that reduces distances infinitely.
At O(VE), it is slower than Dijkstra's O(E log V). It is only preferred when negative edge weights are possible.