Offensive Security Researcher & Quantum Cryptography Analyst

K Shortest Path Algorithm: Working, Explanation, and Implementation

Abdul Wahab Junaid
k shortest path algorithm and working of this algorithm

k shortest path algorithm and working of this algorithm

Most of the time when I think about shortest paths, I only care about the single best route between two points. But I’ve run into plenty of situations where that’s not enough — I want not just the best path, but the second-best, the third-best, and so on, in case the best one is unavailable, restricted, or I simply want alternatives to choose from. This is exactly what the k-shortest paths problem solves: finding the $k$ paths between two nodes with the smallest total costs, ranked from best to worst. The most well-known algorithm for solving this is Yen’s algorithm, and I find it a great example of how a classical algorithm (Dijkstra’s) can be extended into something considerably more powerful with a clever loop-avoidance and deviation strategy on top.

History and Background

The k-shortest paths problem has been studied since the 1950s and 60s, with foundational contributions from several researchers exploring different variants of the problem — whether paths were allowed to repeat vertices (called “loopy” or “loopless with repetition” paths) or required to be simple paths (no repeated vertices). The most widely used algorithm for the loopless k-shortest paths problem was published by Jin Y. Yen in 1971, in a paper titled “Finding the K Shortest Loopless Paths in a Network.” Yen’s algorithm builds directly on top of Dijkstra’s algorithm (or any single-source shortest path algorithm), using a systematic method of generating “deviation” paths that branch off from previously found shortest paths, ensuring no duplicate or looping paths are produced.

Problem Statement

Given a weighted graph $G = (V, E)$, a source vertex $s$, a target vertex $t$, and an integer $k$, I want to find the $k$ simple paths from $s$ to $t$ with the smallest total path weights, ranked in non-decreasing order of total weight.

Core Concepts

How It Works

Yen’s algorithm proceeds as follows:

  1. I find the single shortest path from $s$ to $t$ using Dijkstra’s algorithm (or any suitable shortest path algorithm), and add it to my list $A$ of confirmed shortest paths.
  2. For each subsequent path I want to find (from the 2nd to the $k$-th), I consider every vertex in the previous shortest path as a potential “spur node.”
  3. For each spur node, I temporarily remove the edges that were used by previous shortest paths sharing the same root path up to that spur node (to avoid regenerating a path I’ve already found).
  4. I compute the shortest path from the spur node to the target $t$ in this modified graph.
  5. I combine the fixed root path (from $s$ to the spur node) with this newly computed spur path to form a candidate complete path.
  6. I add all valid candidates generated this way to a candidate list $B$.
  7. I select the candidate in $B$ with the smallest total weight, add it to my confirmed list $A$, and remove it from $B$.
  8. I repeat steps 2-7 until I’ve found $k$ paths or exhausted all candidates.

Working Principle

The key mechanism that makes Yen’s algorithm work is the systematic way it generates every possible “next best” path without missing any candidates and without generating duplicates. By using each vertex of the most recently found shortest path as a spur node, and temporarily blocking edges that would recreate already-found paths sharing the same root, the algorithm guarantees it explores every meaningful deviation from the current best-known paths. Since Dijkstra’s algorithm (used to compute each spur path) always finds the true shortest path in the modified graph, and since the overall candidate list is always fully re-evaluated and sorted before selecting the next path, the algorithm is guaranteed to find paths in strictly non-decreasing order of total weight.

Mathematical Foundation

Let $A_i$ denote the $i$-th shortest path found so far, and let the total weight of a path $P$ be:

$$ W(P) = \sum_{e \in P} w(e) $$

For the $i$-th iteration (finding the $i$-th shortest path), given the $(i-1)$-th shortest path $A_{i-1} = (s = v_0, v_1, \ldots, v_m = t)$, I consider each spur node $v_j$ for $j = 0, \ldots, m-1$:

$$ \text{RootPath}_j = (v_0, v_1, \ldots, v_j), \qquad \text{SpurPath}_j = \text{ShortestPath}(v_j, t \mid G’) $$

where $G’$ is the graph with certain edges removed (specifically, the edge leaving $v_j$ that was used by any previously found path sharing the same root path, and all vertices in $\text{RootPath}_j$ except $v_j$ itself, to enforce the simple-path constraint).

The candidate path is:

$$ \text{Candidate}_j = \text{RootPath}_j \cup \text{SpurPath}_j, \qquad W(\text{Candidate}_j) = W(\text{RootPath}_j) + W(\text{SpurPath}_j) $$

I then select:

$$ A_i = \arg\min_{P \in B} W(P) $$

where $B$ is the accumulated candidate list across all spur nodes considered so far (including candidates generated in earlier iterations that weren’t selected yet).

Correctness argument sketch: Since every simple path from $s$ to $t$ must diverge from each previously found shortest path at some vertex (or be identical to one of them), considering every vertex along $A_{i-1}$ as a potential spur node guarantees that the true $i$-th shortest path is included somewhere in the candidate list $B$ by the time I need to select it, assuming $B$ retains all previously generated but unselected candidates across iterations.

Diagrams

flowchart TD
    A["Find shortest path A1 using Dijkstra"] --> B["Add A1 to confirmed list A"]
    B --> C["For i = 2 to k"]
    C --> D["For each spur node in A[i-1]"]
    D --> E["Remove edges/vertices to avoid duplicate/looping paths"]
    E --> F["Compute shortest spur path from spur node to t"]
    F --> G["Combine root path + spur path into candidate"]
    G --> H["Add candidate to list B"]
    H --> I{"More spur nodes?"}
    I -- Yes --> D
    I -- No --> J["Select cheapest candidate from B, add to A"]
    J --> K{"i  C
    K -- No --> L["Return confirmed list A of k shortest paths"]

Pseudocode

YEN-K-SHORTEST-PATHS(G, s, t, k):
    A[1] = DIJKSTRA-SHORTEST-PATH(G, s, t)
    B = empty candidate list

    for i = 2 to k:
        for j = 0 to length(A[i-1]) - 2:
            spurNode = A[i-1][j]
            rootPath = A[i-1][0..j]

            G' = copy of G
            for each path p in A:
                if p[0..j] == rootPath:
                    remove edge (p[j], p[j+1]) from G'

            for each vertex v in rootPath except spurNode:
                remove v from G'

            spurPath = DIJKSTRA-SHORTEST-PATH(G', spurNode, t)

            if spurPath exists:
                totalPath = rootPath + spurPath
                if totalPath not already in B:
                    add totalPath to B

        if B is empty:
            break   // no more paths exist

        A[i] = path in B with minimum total weight
        remove A[i] from B

    return A

Step-by-Step Example

Consider a small graph with vertices $C, D, E, F, G$ and edges: $C$-$D$ (3), $C$-$E$ (2), $D$-$F$ (4), $E$-$D$ (1), $E$-$F$ (2), $D$-$G$ (2), $F$-$G$ (1). I want the 2 shortest paths from $C$ to $G$.

Final result: the 2 shortest paths from $C$ to $G$ both have weight 5, being $C \to E \to D \to G$ and $C \to D \to G$ (with $C \to E \to F \to G$ as the next candidate if I wanted a 3rd).

Time Complexity

Yen’s algorithm runs Dijkstra’s algorithm (or a similar shortest-path algorithm) up to $O(k \cdot V)$ times in the worst case — once for the initial shortest path, and then up to $V$ times (once per spur node) for each of the remaining $k-1$ paths. Since each Dijkstra run costs $O(E + V \log V)$ with a good priority queue implementation, the overall time complexity of Yen’s algorithm is:

$$ O(k \cdot V \cdot (E + V \log V)) $$

Space Complexity

The algorithm requires $O(V + E)$ space for the graph representation, plus $O(k \cdot V)$ space to store the $k$ resulting paths (each of length up to $V$), and $O(V^2)$ in the worst case for the candidate list $B$, since up to $O(V)$ candidates can be generated per iteration across $O(k)$ iterations.

Correctness Analysis

Yen’s algorithm is correct because it systematically and exhaustively considers every possible point of deviation from each previously found shortest path, ensuring the true next-shortest path is always present in the candidate list before it’s selected. The removal of specific edges (those matching the root path of already-found paths) prevents duplicate candidates, and the removal of root-path vertices from the spur-path search space enforces the “simple path” (no revisited vertices) requirement. Since each candidate’s cost is computed via a correct shortest-path algorithm, and the algorithm always selects the minimum-cost candidate available at each step, induction on $i$ shows that $A_1, A_2, \ldots, A_k$ are correctly the $k$ shortest simple paths in non-decreasing order of weight.

Advantages

Disadvantages

Applications

Implementation in C

Implementing the full generality of Yen’s algorithm in C is fairly involved, so here I present a simplified version demonstrating the core mechanism on a small, fixed graph, using an adjacency matrix and a basic Dijkstra’s algorithm as a subroutine.

#include stdio.h>
#include limits.h>
#include string.h>
#include stdbool.h>

#define V 5
#define INF INT_MAX

/* Simple Dijkstra's algorithm returning the shortest distance
   from src to dest in the given graph, or INF if unreachable.
   Also fills path[] with the sequence of vertices (path length in *pathLen). */
int dijkstra(int graph[V][V], int src, int dest, int path[], int *pathLen) {
    int dist[V], prev[V];
    bool visited[V];

    for (int i = 0; i  V; i++) {
        dist[i] = INF;
        prev[i] = -1;
        visited[i] = false;
    }
    dist[src] = 0;

    for (int count = 0; count  V; count++) {
        int u = -1, minDist = INF;
        for (int i = 0; i  V; i++) {
            if (!visited[i] && dist[i]  minDist) {
                minDist = dist[i];
                u = i;
            }
        }
        if (u == -1) break;
        visited[u] = true;

        for (int v = 0; v  V; v++) {
            if (graph[u][v] != 0 && !visited[v] && dist[u] != INF) {
                int newDist = dist[u] + graph[u][v];
                if (newDist  dist[v]) {
                    dist[v] = newDist;
                    prev[v] = u;
                }
            }
        }
    }

    if (dist[dest] == INF) {
        *pathLen = 0;
        return INF;
    }

    /* reconstruct path from dest back to src */
    int temp[V], len = 0;
    int cur = dest;
    while (cur != -1) {
        temp[len++] = cur;
        cur = prev[cur];
    }
    for (int i = 0; i  len; i++) path[i] = temp[len - 1 - i];
    *pathLen = len;

    return dist[dest];
}

int main() {
    /* Vertices: 0=C, 1=D, 2=E, 3=F, 4=G */
    int graph[V][V] = {
        {0, 3, 2, 0, 0},
        {3, 0, 1, 4, 2},
        {2, 1, 0, 2, 0},
        {0, 4, 2, 0, 1},
        {0, 2, 0, 1, 0}
    };

    int path[V], pathLen;
    int dist = dijkstra(graph, 0, 4, path, &pathLen); /* C to G */

    printf("Shortest path distance from C to G: %d\n", dist);
    printf("Path: ");
    const char *names = "CDEFG";
    for (int i = 0; i  pathLen; i++)
        printf("%c ", names[path[i]]);
    printf("\n");

    printf("\nNote: This demonstrates the core Dijkstra subroutine used\n");
    printf("repeatedly inside Yen's algorithm; a full k-shortest-paths\n");
    printf("implementation builds on this by iteratively blocking edges\n");
    printf("and vertices at each spur node, as described in the pseudocode.\n");

    return 0;
}

Sample Input and Output

For the graph described above, finding the shortest path from C to G:

Shortest path distance from C to G: 5
Path: C E D G 

Note: This demonstrates the core Dijkstra subroutine used
repeatedly inside Yen's algorithm; a full k-shortest-paths
implementation builds on this by iteratively blocking edges
and vertices at each spur node, as described in the pseudocode.

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version