Part VI · Graph Algorithms and Tree-Graph Techniques
35. Shortest Paths and Weighted Graph Search
9 lessons•38 topics•Intermediate / Advanced
9 of 9 lessons published
35.015 animated
Shortest path framework
- Relaxation
- Parent reconstruction
- Single-source vs all-pairs
- Negative edges
- Negative cycles
35.024 animated
Unweighted and binary weights
- BFS
- Multi-source BFS
- 0-1 BFS using deque
- Distance layering
35.034 animated
Dijkstra's algorithm
- Nonnegative weights
- Priority queue
- Lazy outdated entries
- Indexed heap
- Path reconstruction
35.044 animated
Bellman-Ford
- Negative edges
- Repeated relaxation
- Negative-cycle detection
- Reachable negative cycles
35.051 animated
SPFA and caveats
- Queue-based relaxation
- Heuristics
- Pathological worst case
- Why SPFA is not guaranteed fast
35.064 animated
Floyd-Warshall
- All-pairs DP
- Intermediate-vertex recurrence
- Negative cycles
- Transitive closure
35.073 animated
Johnson's algorithm
- Reweighting potentials
- Bellman-Ford + Dijkstra
- Sparse all-pairs shortest paths
35.085 animated
A* and heuristics
- Admissible heuristics
- Consistency
- Euclidean/Manhattan heuristics
- Open/closed sets
- Grid search
35.091 animated
Other shortest-path topics
- Bidirectional BFS
- Bidirectional Dijkstra
- K shortest paths overview
- Multicriteria shortest path intro