DEV Community

Akarsh Jaiswal
Akarsh Jaiswal

Posted on

Finding the K Shortest Paths Using Yen's Algorithm in Python

#dijkstra #graph #shortestpath #yens

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 networkx and 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:

  1. Starts with the shortest path (via Dijkstra)
  2. Iteratively finds deviations ("spur paths") from previous paths
  3. Ensures no cycles and avoids previously used subpaths
  4. Returns a list of the top k paths 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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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}")
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Performance Note

  • networkx is fine for small to mid-sized graphs.
  • For very large graphs, you might want to use igraph or 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)