Mixed Practice - Shortest Paths
You've learned BFS, Dijkstra, Bellman-Ford, and Floyd-Warshall. Now practice mixing them together.
Lessons
1. Intro
(Choosing the right algorithm)
2. The Decision Tree
(Four questions to ask)
3. Quiz: Algorithm Selection
Knowledge check
4. When BFS Wins
(Unweighted graphs only)
5. When Dijkstra Wins
(Non-negative weights)
6. Quiz: Dijkstra Traps
Knowledge check
7. When Bellman-Ford Wins
(Negative weights allowed)
8. Negative Cycles: The Trap
(Not always infinite)
9. Quiz: Negative Cycles
Knowledge check
10. When Floyd-Warshall Wins
(All-pairs, small graphs)
11. CSES 1671 Shortest Routes I - Problem Statement
(CSES - Dijkstra)
12. CSES 1671 Shortest Routes I - Recognizing Dijkstra
(Single-source, non-negative)
13. CSES 1671 Shortest Routes I - Implementation Notes
(Priority queue tricks)
14. Quiz: Dijkstra Optimization
Knowledge check
15. CSES 1671 Shortest Routes I - Implementation
(C++ code)
16. CSES 1673 High Score - Problem Statement
(CSES - Bellman-Ford trap)
17. CSES 1673 High Score - The Maximum-Score Trick
(Negate and minimize)
18. CSES 1673 High Score - The Reachability Trap
(Not all cycles matter)
19. Quiz: Negative Cycle Impact
Knowledge check
20. CSES 1673 High Score - Implementation
(Bellman-Ford + BFS)
21. CSES 1195 Flight Discount - Problem Statement
(CSES - State-space Dijkstra)
22. CSES 1195 Flight Discount - State-Space Graphs
(Tracking coupon usage)
23. CSES 1195 Flight Discount - Transitions
(Two types of edges)
24. Quiz: State Graph Size
Knowledge check
25. CSES 1195 Flight Discount - Implementation
(State Dijkstra)
26. CSES 1202 Investigation - Problem Statement
(CSES - Dijkstra + counting)
27. CSES 1202 Investigation - Counting During Dijkstra
(Four arrays)
28. CSES 1202 Investigation - Update Rules
(When relaxing u→v)
29. Quiz: Counting Paths
Knowledge check
30. CSES 1202 Investigation - Implementation
(Extended Dijkstra)
31. Codeforces 295B Greg and Graph - Problem Statement
Codeforces 295B - Reverse F...
32. Codeforces 295B Greg and Graph - The Reverse Trick
(Process deletions backward)
33. Codeforces 295B Greg and Graph - Floyd-Warshall Incremental
(Adding one node at a time)
34. Quiz: Reverse Processing
Knowledge check
35. Codeforces 295B Greg and Graph - Implementation
(Reverse Floyd-Warshall)
36. Section Recap
(What you practiced)