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 2 Time Complexity
Time Complexity (category)Polynomial Time -- O(n^k) 1 Connections
In Field
Source Wikipedia: Yen's algorithm
Sources
1. Yen's Algorithm (Wikipedia)
Wikipedia infobox: time complexity polynomialQuote, Wikipedia infobox: time complexity polynomial
polynomial
2. 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.
In Field: Algorithms and Complexity Theory, Lead sentence
Yen's algorithm computes single-source K-shortest loopless paths for a graph with non-negative edge cost.
View the SourceWikidata: Yen's Algorithm
Wikidata Q8052172, class allow-list match (w-wdresolver-0926)View the Source Reader 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.