Bellman-Ford Algorithm
Dijkstra breaks with negative edges. Bellman-Ford handles them and detects negative cycles. You'll learn when to use each algorithm.
Lessons
1. Intro
(Why you need it)
2. When Dijkstra Fails
(Negative edge problem)
3. The Relaxation Operation
(Core building block)
4. Bellman-Ford Strategy
(Relax all edges repeatedly)
5. Why $n-1$ Iterations
(Maximum path length)
6. Basic Bellman-Ford Implementation
(The algorithm)
7. Time Complexity Analysis
(Why it's slower)
8. Quiz: Relaxation and Iterations
Knowledge check
9. Detecting Negative Cycles
(The $n$-th iteration)
10. Finding Affected Nodes
(Reachability from cycle)
11. CSES 1673 High Score - Problem Statement
(CSES 1673)
12. CSES 1673 High Score - Negating Weights
(Maximum becomes minimum)
13. CSES 1673 High Score - Detecting Positive Cycles
(In the original graph)
14. CSES 1673 High Score - Two-Way Reachability
(Cycle must matter)
15. CSES 1673 High Score - Algorithm
(Step-by-step approach)
16. CSES 1673 High Score - Implementation
(Pseudocode walkthrough)
17. CSES 1673 High Score - Walkthrough
(Trace execution)
18. CSES 1673 High Score - Lessons
(summary)
19. Quiz: Negative Cycle Reachability
Knowledge check
20. CSES 1197 Cycle Finding - Problem Statement
(CSES 1197)
21. CSES 1197 Cycle Finding - Parent Tracking
(Reconstructing the cycle)
22. CSES 1197 Cycle Finding - Finding Cycle Start
(Inside the cycle)
23. CSES 1197 Cycle Finding - Algorithm
(Detection and extraction)
24. CSES 1197 Cycle Finding - Implementation
(Pseudocode walkthrough)
25. CSES 1197 Cycle Finding - Walkthrough
(Trace execution)
26. CSES 1197 Cycle Finding - Lessons
(summary)
27. Quiz: Cycle Reconstruction
Knowledge check
28. LeetCode 787 Cheapest Flights Within K Stops - Problem Statement
(LeetCode 787)
29. LeetCode 787 Cheapest Flights Within K Stops - Layer-by-Layer Relaxation
(Limiting path length)
30. LeetCode 787 Cheapest Flights Within K Stops - Temporal Separation
(Why two arrays matter)
31. LeetCode 787 Cheapest Flights Within K Stops - Algorithm
(Modified Bellman-Ford)
32. LeetCode 787 Cheapest Flights Within K Stops - Implementation
(Pseudocode walkthrough)
33. LeetCode 787 Cheapest Flights Within K Stops - Walkthrough
(Trace execution)
34. LeetCode 787 Cheapest Flights Within K Stops - Lessons
(summary)
35. Quiz: Bounded Relaxation
Knowledge check
36. SPFA Improvement
(Queue-based relaxation)
37. SPFA Implementation
(Queue-based approach)
38. SPFA Cycle Detection
(Counting relaxations)
39. When to Use Bellman-Ford
(Dijkstra vs Bellman-Ford)
40. Application: Currency Arbitrage
(Detecting profit cycles)
41. Quiz: Algorithm Selection
Knowledge check
42. Application: Network Routing
(Handling link costs)
43. Edge Cases and Mistakes
(What can go wrong)
44. Comparison Summary
(Algorithm characteristics)
45. Common Mistakes
(What to avoid)
46. Quiz: SPFA Worst Case
Knowledge check
47. Practice Strategy
(How to internalize this)
48. Section Recap
(What you learned)