Shortest Paths Practice Questions
Eight interview classics covering every algorithm in the chapter. Each problem is a direct instance of BFS, Dijkstra, Bellman-Ford, or Floyd-Warshall — once you recognize which one, the code writes itself.
Before reading any solution, force yourself through the decision flow:
- Equal weights? → BFS
- Single source, non-negative? → Dijkstra
- Negative edges? → Bellman-Ford
- All pairs, small V? → Floyd-Warshall
- Constraint on edge count? → modified Bellman-Ford / expanded-state Dijkstra
Five questions. Four algorithms. The whole chapter.
Easy
| Problem | Pattern | Status |
|---|---|---|
| Network Delay Time | Dijkstra → take max distance | Available |
| Shortest Path in Binary Matrix | BFS on an implicit 8-connected grid | Available |
Medium
| Problem | Pattern | Status |
|---|---|---|
| Cheapest Flights Within K Stops | Bellman-Ford limited to K+1 passes (or expanded Dijkstra) | Available |
| Path with Minimum Effort | Modified Dijkstra — replace sum with max | Available |
| Find City With Smallest Number of Neighbors | Floyd-Warshall all-pairs | Available |
| The Maze II | Dijkstra on a grid with “rolling ball” edge weights | Available |
Hard
| Problem | Pattern | Status |
|---|---|---|
| Word Ladder | BFS on an implicit string-mutation graph | Available |
| Swim in Rising Water | Dijkstra-style minimax on a grid | Available |
More Practice (Coming Soon)
| Problem | Pattern | Status |
|---|---|---|
| Shortest Path Visiting All Nodes | Bitmask BFS | Coming Soon |
| Reachable Nodes In Subdivided Graph | Dijkstra + edge subdivision | Coming Soon |
| Bus Routes | BFS over routes-as-vertices | Coming Soon |
| Minimum Cost to Reach Destination in Time | Constrained Dijkstra | Coming Soon |
| Number of Ways to Arrive at Destination | Dijkstra + path counting | Coming Soon |
| Minimum Number of Refueling Stops | Dijkstra-flavored DP | Coming Soon |
| Currency Arbitrage | Bellman-Ford negative cycle detection | Coming Soon |
| Second Minimum Time to Reach Node | Modified Dijkstra tracking two best distances | Coming Soon |