Finding the K Shortest Paths Using Yen’s Algorithm in Python – ██FR█████ █INTELL███████████

This content originally appeared on DEV Community and was authored by Akarsh Jaiswal

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:

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 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

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

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.

This content originally appeared on DEV Community and was authored by Akarsh Jaiswal