Floyd-Warshall Algorithm
All-pairs shortest paths. Dynamic programming on graphs. Finding distances between every pair of nodes.
Lessons
1. Intro
(All-pairs shortest paths)
2. The All-Pairs Problem
Finding every pair's distance
3. Naive Approach
(Running Dijkstra n times)
4. The Core Idea
Paths through intermediate ...
5. The DP State
(Using vertices 0 to k)
6. Space Improvement
(Overwriting in place)
7. Quiz: Floyd-Warshall DP State
Knowledge check
8. Why k is Outermost
(Correctness depends on order)
9. The Algorithm
(Three nested loops)
10. Time Complexity
(Cubic in vertices)
11. Handling Negative Edges
(Unlike Dijkstra it works)
12. Detecting Negative Cycles
(Checking the diagonal)
13. Quiz: Negative Edges in Floyd-Warshall
Knowledge check
14. Path Reconstruction
(Storing next hops)
15. Transitive Closure
Reachability instead of dis...
16. When to Use Floyd-Warshall
(vs running Dijkstra n times)
17. Quiz: When to Use Floyd-Warshall
Knowledge check
18. CSES 1672 Shortest Routes II - Problem Statement
(CSES 1672 walkthrough intro)
19. CSES 1672 Shortest Routes II - Why Floyd-Warshall Fits
(All-pairs in one shot)
20. CSES 1672 Shortest Routes II - Handling Multiple Edges
(Taking the minimum weight)
21. CSES 1672 Shortest Routes II - Implementation
(Using adjacency matrix)
22. CSES 1672 Shortest Routes II - Walkthrough
(Step-by-step trace)
23. CSES 1672 Shortest Routes II - Lessons
(Precomputation wins)
24. LeetCode 1334 Find the City - Problem Statement
LeetCode 1334 walkthrough i...
25. LeetCode 1334 Find the City - Breaking Down the Problem
(Two-step approach)
26. LeetCode 1334 Find the City - Counting Reachable Cities
(Looping through distances)
27. LeetCode 1334 Find the City - Implementation
(Using Floyd-Warshall)
28. LeetCode 1334 Find the City - Walkthrough
(LeetCode example trace)
29. LeetCode 1334 Find the City - Lessons
Post-processing distance ma...
30. Quiz: Floyd-Warshall Path Reconstruction
Knowledge check
31. Common Mistakes
(Mistakes to avoid)
32. Floyd-Warshall vs Bellman-Ford
(Two ways to handle negatives)
33. Floyd-Warshall vs Johnson's Algorithm
(Sparse graphs with negatives)
34. Practical Constraints
(When n³ is acceptable)
35. Memory Layout
(Using 2D array efficiently)
36. Infinity Handling
(Avoiding overflow)
37. Undirected Graphs
(Symmetric distance matrix)
38. Variants of Floyd-Warshall
(Minimax and maximin paths)
39. Quiz: Floyd-Warshall Loop Order
Knowledge check
40. Practice Problems
(Build your skills)
41. Section Recap
(What you learned)