Dijkstra's Algorithm
Priority queue implementation, lazy deletion, proof of correctness, and optimizations.
Lessons
1. Intro
Why BFS is not enough for weighted graphs
2. Introducing Weights
Edge weights and their meanings
3. The Greedy Strategy
Dijkstra's key insight
4. Dijkstra's Algorithm - Setup
Initialization and data structures
5. Dijkstra's Algorithm - The Loop
Processing nodes in order
6. The Relaxation Step
Updating distances through edges
7. Quiz: Dijkstra's Greedy Choice
Knowledge check
8. Relaxation in Code
Complete code walkthrough
9. Dijkstra - Implementation
Full pseudocode
10. Complexity of Dijkstra
Time and space analysis
11. Path Reconstruction in Dijkstra
Tracking the actual path
12. Handling Large Weights
Overflow and precision concerns
13. Quiz: Why Negative Edges Break Dijkstra
Knowledge check
14. LeetCode 743 Network Delay Time - Problem Statement
Find minimum time for signal propagation
15. LeetCode 743 Network Delay Time - Intuition
Understanding the problem
16. LeetCode 743 Network Delay Time - Implementation
Code solution
17. CSES 1671 Shortest Routes I - Problem Statement
Path reconstruction challenge
18. LeetCode 1514 Path with Maximum Probability - Problem Statement
Adapting Dijkstra for products
19. LeetCode 1514 Path with Maximum Probability - Modifying Dijkstra
Different metrics and objectives
20. Quiz: Dijkstra Modifications
Knowledge check
21. LeetCode 787 Cheapest Flights Within K Stops - Problem Statement
Dijkstra with constraints
22. LeetCode 787 Cheapest Flights Within K Stops - State Definition
Expanded state space
23. LeetCode 787 Cheapest Flights Within K Stops - Algorithm
Modified Dijkstra approach
24. LeetCode 787 Cheapest Flights Within K Stops - Visited Set
Revisiting nodes in expanded state
25. LeetCode 787 Cheapest Flights Within K Stops - Implementation
Code solution
26. LeetCode 787 Cheapest Flights Within K Stops - Lessons
Key takeaways
27. Quiz: Dijkstra with Constraints
Knowledge check
28. LeetCode 1631 Path with Minimum Effort - Problem Statement
Minimax path problem
29. LeetCode 1631 Path with Minimum Effort - Minimax Path
Maximum edge on path
30. LeetCode 1631 Path with Minimum Effort - Algorithm
Modified Dijkstra for minimax
31. LeetCode 1631 Path with Minimum Effort - Priority Queue
Heap structure for grid
32. LeetCode 1631 Path with Minimum Effort - Implementation
Code solution
33. LeetCode 1631 Path with Minimum Effort - Lessons
When to use minimax Dijkstra
34. Quiz: Dijkstra on Grids
Knowledge check
35. CSES 1195 Flight Discount - Problem Statement
One-time discount optimization
36. CSES 1195 Flight Discount - State Definition
Tracking discount usage
37. CSES 1195 Flight Discount - Algorithm
Two-state Dijkstra
38. CSES 1195 Flight Discount - Implementation
Code solution
39. CSES 1195 Flight Discount - Lessons
State expansion patterns
40. Section Recap
Summary