Shortest Paths with Negative Weights and Between All Pairs
Dijkstra's greedy choice fails once an edge can reduce a cost, so Bellman-Ford relaxes every edge n minus one times instead, and reports a negative cycle if anything still improves. Floyd-Warshall answers every pair at once by asking which intermediate vertices are allowed.
What a learner can do afterwards
- Build a graph with a negative edge where Dijkstra returns the wrong distance
- Run Bellman-Ford and say what an improvement on the last pass proves
- Explain what the third index in the Floyd-Warshall recurrence stands for
1 · Read
Dijkstra locks in each vertex greedily and never looks back. A negative edge can later undercut a locked distance. One graph with a single reducing edge is enough to return the wrong answer.
Start S links to A at cost 5 and to B at cost 6, and B links to A at minus 4. Dijkstra locks A at 5, but the path through B costs 2. The greedy lock missed the cheaper route.
Bellman-Ford relaxes every edge n minus one times instead of locking anything. If any edge still improves on the last pass, a negative cycle exists. That improvement is the proof.
Floyd-Warshall answers every pair at once. Its third index names which intermediate vertices may be used so far. Grow the allowed set step by step and the table converges to all-pairs answers.
Greedy fails on negative edges, full relaxation detects cycles, and allowed vertices build all pairs.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.