Dijkstra’s Algorithm
Map of notes covering Dijkstra’s shortest-path algorithm — the foundational greedy approach for single-source shortest paths in non-negative-weight graphs.
Foundational
- Dijkstra’s Algorithm - The Greedy Invariant — why the algorithm works (proof of optimality, when the invariant breaks)
- Shortest Path Relaxation Operation — the core update operation Dijkstra builds on
Implementation
- Dijkstra’s Algorithm - Implementation Patterns — heap choice, visited set, lazy vs eager updates, path reconstruction, early termination, common bugs
Comparison & Context
- Bellman-Ford Algorithm - Edge Relaxation Pattern — when negative weights exist
- Bellman-Ford Algorithm - Negative Weight Handling — what breaks under negative weights
- Floyd-Warshall - All-Pairs Dynamic Programming — when you need all-pairs shortest paths
- BFS as Wavefront Propagation — unweighted shortcut (Dijkstra reduces to BFS when all weights = 1)
- Graph Algorithms — broader algorithms hub
- Graph Algorithms Optimal Complexity — complexity comparisons across algorithms
Quick Decision Guide
| Situation | Use |
|---|---|
| Single-source, non-negative weights | Dijkstra |
| Single-source, negative weights | Bellman-Ford Algorithm - Edge Relaxation Pattern |
| All-pairs shortest paths | Floyd-Warshall - All-Pairs Dynamic Programming |
| Unweighted graph | BFS as Wavefront Propagation |
| Heuristic available (target-known) | A* (Dijkstra + heuristic) |