Week 42 of 43
CP Track
WEEK 42 LEARNING MODULE
Shortest Path Algorithms: Dijkstra, Bellman-Ford, Floyd-Warshall
Covers Single-Source and All-Pairs shortest path algorithms: Dijkstra ($O((V+E)\log V)$), Bellman-Ford ($O(V \cdot E)$ with negative cycle detection), SPFA ($O(E)$ avg), and Floyd-Warshall ($O(V^3)$).
6 Practice Problems4 Core ConceptsVerified Curriculum: high Confidence
What You'll Learn
- ✓Master Single-Source and All-Pairs Shortest Path algorithms on weighted graphs.
- ✓Implement Dijkstra's Algorithm using a Min-Heap / Priority Queue for non-negative edge weights in $O((V + E) \log V)$ time.
- ✓Implement Bellman-Ford Algorithm in $O(V \cdot E)$ time with negative edge weights and Negative Cycle Detection.
- ✓Implement Shortest Path Faster Algorithm (SPFA) with average $O(E)$ time.
- ✓Implement Floyd-Warshall Algorithm for All-Pairs Shortest Path in $O(V^3)$ time and $O(V^2)$ space.
Core Concepts
Edge Relaxation Principle
O(1)Updating dist[v] = min(dist[v], dist[u] + weight(u, v)) when a shorter path via u is discovered.
Dijkstra's Algorithm
O((V + E) * log V) time, O(V) spaceGreedy single-source shortest path using a min-heap; requires non-negative edge weights.
Bellman-Ford & Negative Cycles
O(V * E) time, O(V) spaceRelaxing all E edges V-1 times; a further relaxation on the V-th pass proves the existence of a negative cycle.
Floyd-Warshall All-Pairs Algorithm
O(V³) time, O(V²) spaceDynamic programming evaluating dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) for all intermediate vertices k.
Algorithms Covered
Dijkstra's Algorithm ($O((V + E) \log V)$)Bellman-Ford Algorithm ($O(V \cdot E)$)Negative Cycle DetectionShortest Path Faster Algorithm (SPFA)Floyd-Warshall Algorithm ($O(V^3)$)
Data Structures Applied
Weighted GraphsMin-Heap / Priority QueueDistance Arrays / Matrices
“To find the shortest path, sometimes you have to be willing to take the longer journey.”
— Unknown