ExtendedSource checked

Yen's K Shortest Paths

Finds several shortest loopless paths between the same two nodes.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Pathfinding
Difficulty: Advanced
Family: K Shortest Paths
Tier: Extended
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 2
Code example: Not ready
Visualization: Ready
Aliases: Yen's Algorithm

Overview

Yen's algorithm repeatedly deviates from previously found paths and keeps candidate alternatives in sorted order.

Core Concepts

distance relaxationpath rankingedge weightsgraph representationk shortest pathsroute costfrontier expansionpath reconstruction

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(K E log V)

Average

O(K V (E + V log V))

Worst

O(K V (E + V log V))

Space

O(KV)

When to Use

Use Yen's K Shortest Paths when you need to find the shortest path first.
Use it for route alternatives with inputs like weighted graph.
Use it when routes have explicit movement rules, costs, obstacles, or graph edges.
Use it when the K Shortest Paths tradeoff is acceptable for the problem size.

When Not to Use

Avoid it when edge costs or movement constraints do not match the algorithm's assumptions.
Avoid it when the required output is not ordered list of loopless paths.

What It Does

Finds the shortest path first
Generates ranked path alternatives

Use Cases

Route alternatives
Network failover planning
Path diversity analysis

Inputs

Weighted graph
Start node
Goal node
Number of paths

Outputs

Ordered list of loopless paths

Key Formulas (1)

Candidate path cost

cost(candidate) = cost(root_path) + cost(spur_path)

cost(candidate) = cost(root_path) + cost(spur_path)

Ranks each alternate path built from a fixed root path and a new spur path.

Pseudocode

1.Find the first shortest path
2.For each node in the last path, create a spur path
3.Temporarily remove edges that would duplicate earlier paths
4.Store valid candidates in a priority queue
5.Choose the next best candidate until K paths are found

Canonical Example

Input: edges = A-B: 1, B-C: 2, A-C: 5; start = A; goal = C
Output: path = A -> B -> C, cost = 3
Explanation: Yen's K Shortest Paths: The algorithm compares route costs and selects the cheaper path through B.

Implementation Notes

Keep the input contract explicit: Weighted graph; Start node; Goal node; Number of paths.
Use this step as the implementation spine: Find the first shortest path.
Then preserve the next state change: For each node in the last path, create a spur path.
Keep node ids, edge direction, and visited state explicit in the implementation.
Store predecessor links if the final path is needed, not just the final distance.

Common Pitfalls

Yen's algorithm is for loopless paths and can become expensive as K grows.
Not defining directed versus undirected edges clearly can change the result.
Treating a visited node as final before its best known cost is actually settled.
Returning ordered list of loopless paths without handling empty, invalid, or boundary inputs.

Interactive Mechanism Walkthrough

2D Grid Wavefront & Trajectory

Show a best route and ranked deviations from it.

Step 1 of 5: Find the first shortest path

path-alternatives

Notes

Yen's K Shortest Paths operates in O(K V (E + V log V)) time and O(KV) space within the K Shortest Paths family. Key governing relation: cost(candidate) = cost(root_path) + cost(spur_path). Often compared with Dijkstra's Algorithm and Johnson's Algorithm.