When you need more than just the single shortest path—say, the top 3 shortest routes between two locations—Dijkstra alone isn't enough. That's where Yen's algorithm comes in. It builds on Dijkstra’s algorithm to find multiple shortest paths in a weighted graph.
In this post, we'll:
- Explain Yen’s K Shortest Paths algorithm
- Implement it using
networkxand Dijkstra - Run an example to get multiple optimal routes
No external packages beyond networkx required.
What is Yen’s Algorithm?
Yen’s algorithm finds the K shortest loopless paths between a source and target node in a weighted graph. It:
- Starts with the shortest path (via Dijkstra)
- Iteratively finds deviations ("spur paths") from previous paths
- Ensures no cycles and avoids previously used subpaths
- Returns a list of the top
kpaths ranked by total weight
This is helpful in routing, logistics, or network failover systems where alternate optimal paths are needed.
Prerequisites
Install networkx if you don’t already have it:
pip install networkx
Full Implementation of Yen’s Algorithm in Python
Here’s a complete implementation using networkx. This assumes a directed graph with positive edge weights.
import heapq
import networkx as nx
def dijkstra_path_length(graph, source, target):
try:
return nx.dijkstra_path_length(graph, source, target, weight='weight')
except nx.NetworkXNoPath:
return float('inf')
def yen_k_shortest_paths(graph, source, target, k):
if source == target:
return [[source]]
paths = []
potential_paths = []
# First shortest path using Dijkstra
try:
first_path = nx.dijkstra_path(graph, source, target, weight='weight')
paths.append(first_path)
except nx.NetworkXNoPath:
return []
for i in range(1, k):
for j in range(len(paths[-1]) - 1):
spur_node = paths[-1][j]
root_path = paths[-1][:j + 1]
g_copy = graph.copy()
# Remove edges that would recreate previously found paths
for path in paths:
if path[:j + 1] == root_path and len(path) > j + 1:
g_copy.remove_edge(path[j], path[j + 1])
# Remove nodes in root path except spur_node
for node in root_path[:-1]:
g_copy.remove_node(node)
try:
spur_path = nx.dijkstra_path(g_copy, spur_node, target, weight='weight')
total_path = root_path[:-1] + spur_path
total_weight = sum(
graph[u][v]['weight'] for u, v in zip(total_path, total_path[1:])
)
heapq.heappush(potential_paths, (total_weight, total_path))
except nx.NetworkXNoPath:
continue
if potential_paths:
_, new_path = heapq.heappop(potential_paths)
paths.append(new_path)
else:
break
return paths
Example Usage
G = nx.DiGraph()
G.add_weighted_edges_from([
('A', 'B', 1),
('A', 'C', 5),
('B', 'C', 1),
('B', 'D', 2),
('C', 'D', 1),
('D', 'E', 3),
('C', 'E', 5),
])
k_paths = yen_k_shortest_paths(G, 'A', 'E', k=3)
for idx, path in enumerate(k_paths):
cost = sum(G[u][v]['weight'] for u, v in zip(path, path[1:]))
print(f"{idx + 1}: Path = {path}, Cost = {cost}")
Output:
1: Path = ['A', 'B', 'C', 'D', 'E'], Cost = 7
2: Path = ['A', 'B', 'D', 'E'], Cost = 6
3: Path = ['A', 'C', 'D', 'E'], Cost = 9
Performance Note
-
networkxis fine for small to mid-sized graphs. - For very large graphs, you might want to use
igraphor implement a more efficient priority queue system.
When Should You Use Yen’s Algorithm?
Use it when:
- You need multiple options for routing
- You want to offer fallbacks (e.g., in navigation systems)
- Your problem requires loopless, shortest, and alternative paths
Don’t use it for cyclic paths or in graphs with negative weights—it assumes non-negative weighted edges.
Final Thoughts
Yen’s algorithm is a great way to go beyond "just the shortest path" in a network. While libraries like networkx don't offer it out-of-the-box, it's easy to implement yourself using Dijkstra as the base. Whether you're building logistics tools, recommendation engines, or network analysis apps, having access to the K best paths opens up new possibilities.
Top comments (0)