Yen's Algorithm — K Shortest Loopless Paths
Seed with Dijkstra, then derive candidates via spur nodes, edge/node removal, and a candidate heap B.
Time: O(K · V · (E + V log V))
Space: O(K · V + E)
Loopless (simple) paths
Slow
Fast
K = 3
Default edge/node
Accepted path
Spur path / candidate
Removed edge/node
Spur node
Root path
Graph (source C → target H)
Step 0/0
Spur Dijkstras: 0
|A|: 0
|B|: 0
What's happening
Press Start to run Yen's algorithm, or Step to advance one step at a time.
Accepted set A / Candidate heap B
A = [ ]
B = [ ]
Big-O
| Operation | Cost |
|---|
| One Dijkstra (spur path) | O(E + V log V) |
| Spur nodes per path | O(V) |
| Total (K paths) | O(K · V · (E + V log V)) |
| Heap push / pop | O(log(K·V)) |
Operation log