Yen's algorithm finds the K shortest loopless paths between a source and a destination node in a weighted graph, starting from the single shortest path found by a standard shortest path method and then systematically generating candidate deviation paths by temporarily removing edges and nodes already used by shorter paths already found, selecting the best candidate at each step to extend the list. Jin Y. Yen published the method in 1971. It is widely used in routing applications that need not just the single best path but a ranked list of alternative routes.
Facts
Time ComplexityO(KN(M + N log N)) using Dijkstra with a Fibonacci heap 1 Sources
1. Wikipedia: Yen's algorithm
Lead section
The algorithm was published by Jin Y. Yen in 1971 and employs any shortest path algorithm to find the best path, then proceeds to find K − 1 deviations of the best path.
Performance section
The time complexity of Yen's algorithm is dependent on the shortest path algorithm used in the computation of the spur paths, so the Dijkstra algorithm is assumed.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.