Yen's algorithm for k shortest paths | CS 61B | Ludwig Explains

Dijkstra's algorithm gives you THE shortest path from s to t. But what if you want the second shortest? The third? A ranked list of routes you can fall back on if the primary fails?

That's what Yen's algorithm does. It finds the k shortest loopless paths in a weighted graph. The mechanism is surprisingly clean: every new shortest path must DEVIATE from a previous one at some node. So you enumerate candidate deviations — root path agrees with the previous winner up to node v, then a new "spur" runs Dijkstra from v to t — forbid the edges that would let you rediscover an existing path, and pick the cheapest candidate. Repeat k times.

This video walks through:
- The problem statement (k shortest loopless paths)
- The key insight: deviation points along a known path
- How to compute a deviation: edge removal + forbidden root nodes + Dijkstra
- The full algorithm (A = confirmed paths, B = candidate priority queue)
- A worked example on a 5-node graph
- Time complexity: O(k · n · (m + n log n))
- Where Yen's shows up in practice (network routing, alternate routes, fault tolerance, bioinformatics)

Reference: Yen, J. Y. (1971). "Finding the K Shortest Loopless Paths in a Network." Management Science 17(11): 712–716.

Subscribe for more "making the confusing click": https://youtube.com/@LudwigExplains

#cs #algorithms #graphtheory #shortestpaths #dijkstra #LudwigExplains #cs61b

Видео Yen's algorithm for k shortest paths | CS 61B | Ludwig Explains канала ludwig explains