Opening Shortest Paths
Shortest Paths
- Length
- 57 min
- Level
- Undergraduate
- Recorded
- MIT2013
Chapter 1 of 4: Before the lecture
Costan reduces weighted, parity-constrained and traffic-dependent shortest paths to plain BFS and Dijkstra runs.
Shortest paths in graphs with edge weights, parity constraints, and time-dependent costs are solved using graph transformations rather than designing new algorithms. The lecture demonstrates how to map modified shortest path problems into standard formats suited for Dijkstra's algorithm and Breadth-First Search. It builds concrete transformations for graphs with integer weights, paths with alternating parity, and time-expanded networks with varying traffic conditions.
Shortest paths in graphs with edge weights, parity constraints, and time-dependent costs are solved using graph transformations rather than designing new algorithms. The lecture demonstrates how to map modified shortest path problems into standard formats suited for Dijkstra's algorithm and Breadth-First Search. It builds concrete transformations for graphs with integer weights, paths with alternating parity, and time-expanded networks with varying traffic conditions.

This lecture
Lecture 29 of 31 of Introduction to Algorithms.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.
Your comment is kept while you sign up.Sign in