Shortest Path Algorithms
MediumPick the right shortest-path tool
Problem
Compare BFS, Dijkstra, Bellman-Ford and Floyd-Warshall and when each applies.
Unweighted: BFS; non-negative weights: Dijkstra; negatives: Bellman-Ford; all pairs: Floyd-Warshall.
The idea
There is no single 'shortest path' algorithm — you choose by the graph. Unweighted? Plain BFS. Non-negative weights from one source? Dijkstra (shown here). Negative edges? Bellman-Ford. Every pair at once? Floyd-Warshall. This demo walks through Dijkstra, the workhorse for weighted single-source shortest paths.
Step 1 of 13. Goal: the shortest distance from A to every other node. Start A = 0, everyone else = ∞ (unknown). dist [0, ∞, ∞, ∞, ∞], settled —.
1dist[src] = 0, all others = ∞2min-heap H = {(0, src)}3while H not empty:4 (d, u) = pop-smallest from H5 for each edge (u → v, weight w):6 if d + w < dist[v]:7 dist[v] = d + w; push (dist[v], v)8return distInput
- nodes
- 5, 6 edges
Memory
- dist
- [0, ∞, ∞, ∞, ∞]
- frontier
- —
Output
- settled
- —
- shortest dist
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Example
- Input:
- unweighted vs weighted
- Output:
- pick the right one
Finished the walkthrough? Add it to your streak.