Shortest Path Variants
You know Dijkstra and BFS. Now extend them with state-space search. Solve grid problems with obstacle elimination and multi-constraint shortest paths.
Lessons
1. Introduction to Shortest Path Variants
Beyond basic BFS and Dijkstra
2. What Shortest Path Variants Solve
Constraints that change the algorithm
3. When to Use Each Algorithm
BFS vs 0-1 BFS vs Dijkstra
4. State-Space BFS Pattern
The BFS state encoding
5. Problem - Grid with Obstacles Elimination
LC 1293 - eliminate k obstacles
6. Grid with Obstacles Elimination - Why Naive Fails
State = (row, col, remaining)
7. Grid with Obstacles Elimination - Defining the DP
3D state: position + resource
8. Grid with Obstacles Elimination - Transition
Empty = free, obstacle = costs 1
9. Grid with Obstacles Elimination - Base Cases
1×1 grid, k ≥ path length
10. Grid with Obstacles Elimination - Implementation
3D visited array or tuple set
11. Grid with Obstacles Elimination - Time and Space
O(m·n·k) states visited once
12. 0-1 BFS - The Deque Trick
Binary weight optimization
13. Min Cost Valid Path - Why 0-1 BFS?
Choosing the right algorithm
14. Ways to Arrive - Counting Shortest Paths
Counting optimal routes
15. Problem - Min Cost Valid Path
LC 1368 - arrows and direction changes
16. Min Cost Valid Path - Solution
0-1 BFS: free if arrow matches
17. Problem - Ways to Arrive
LC 1976 - count shortest paths
18. Ways to Arrive - Solution
dist[v] + ways[v] together
19. Quiz: Pattern Recognition
Which algorithm fits?
20. Quiz: Edge Cases
Negative edges, disconnected graphs
21. Common Mistakes in Shortest Path
Wrong algorithm, missing copy
22. Problem - Reachable Nodes In Subdivided Graph
LC 882 - subdivided edges
23. Reachable Nodes In Subdivided Graph - Solution
The solution
24. Problem - Shortest Path with Alternating Colors
LC 1129 - alternating edges
25. Shortest Path with Alternating Colors - Solution
The solution
26. Problem - Shortest Path Visiting All Nodes
LC 847 - visit all nodes
27. Shortest Path Visiting All Nodes - Solution
The solution
28. Problem - Minimum Weighted Subgraph
LC 2203 - weighted subgraph
29. Minimum Weighted Subgraph - Solution
The solution
30. Section Recap
State expansion to minimax paths