# Yen's algorithm

Yen's algorithm computes single-source K-shortest loopless paths for a graph with non-negative edge cost. The algorithm was published by Jin Y. Yen in 1971 and employs any shortest path algorithm to find the best path, then proceeds to find K − 1 deviations of the best path. Template:Tree search algorithm

## Algorithm

### Description

The algorithm can be broken down into two parts, determining the first k-shortest path, $A^{1}$ , and then determining all other k-shortest paths. It is assumed that the container $A$ will hold the k-shortest path, whereas the container $B$ , will hold the potential k-shortest paths. To determine $A^{1}$ , the shortest path from the source to the sink, any efficient shortest path algorithm can be used.

The second process determines a suitable path for $A^{k}$ by finding the path in container $B$ with the lowest cost. This path is removed from container $B$ and inserted into container $A$ and the algorithm continues to the next iteration. Note that if the amount of paths in container $B$ equal or exceed the amount of k-shortest paths that still need to be found, then the necessary paths of container $B$ are added to container $A$ and the algorithm is finished.

### Pseudocode

The algorithm assumes that the Dijkstra algorithm is used to find the shortest path between two nodes, but any shortest path algorithm can be used in its place.

```function YenKSP(Graph, source, sink, K):
// Determine the shortest path from the source to the sink.
A = Dijkstra(Graph, source, sink);
// Initialize the heap to store the potential kth shortest path.
B = [];

for k from 1 to K:
// The spur node ranges from the first node to the next to last node in the shortest path.
for i from 0 to size(A[k − 1]) − 1:

// Spur node is retrieved from the previous k-shortest path, k − 1.
spurNode = A[k-1].node(i);
// The sequence of nodes from the source to the spur node of the previous k-shortest path.
rootPath = A[k-1].nodes(0, i);

for each path p in A:
if rootPath == p.nodes(0, i):
// Remove the links that are part of the previous shortest paths which share the same root path.
remove p.edge(i, i + 1) from Graph;

// Calculate the spur path from the spur node to the sink.
spurPath = Dijkstra(Graph, spurNode, sink);

// Entire path is made up of the root path and spur path.
totalPath = rootPath + spurPath;
// Add the potential k-shortest path to the heap.
B.append(totalPath);

// Add back the edges that were removed from the graph.
restore edges to Graph;

// Sort the potential k-shortest paths by cost.
B.sort();
// Add the lowest cost path becomes the k-shortest path.
A[k] = B;
B.pop();

return A;
```

### Example

Of the three paths in container B, ${A^{2}}_{2}$ is chosen to become $A^{2}$ because it has the lowest cost of 7. This process is continued to the 3rd k-shortest path. However, within this 3rd iteration, note that some spur paths do not exist.And the path that is chosen to become $A^{3}$ is $(C)-(D)-(F)-(H)$ .

## Features

### Time complexity

The time complexity of Yen's algorithm is dependent on the shortest path algorithm used in the computation of the spur paths, so the Dijkstra algorithm is assumed. Dijkstra's algorithm has a worse case time complexity of $O(N^{2})$ , but using a Fibonacci heap it becomes $O(M+N\log N)$ , where $M$ is the amount of edges in the graph. Since Yen's algorithm makes $K$ calls to the Dijkstra in computing the spur paths, the time complexity becomes $O(KN(M+N\log N))$ .

## Improvements

Yen's algorithm can be improved by using a heap to store the potential k-shortest paths of list $B$ . Using a heap as apposed to a list will improve the performance of the algorithm, but not the complexity. One method to slightly decrease complexity is to skip the nodes where there are non-existent spur paths. This case is produced when all the spur paths from a spur node have been used in the previous $A^{k}$ . Also, if container $B$ has $K-k$ paths of minimum length, in reference to those in container $A$ , then they can be extract and inserted into container $A$ since no shorter paths will be found.

### Lawler's modification

Eugene Lawler proposed a modification to Yen's algorithm in which duplicates path are not calculated as opposed to the original algorithm where they are calculated and then discarded when they are found to be duplicates. These duplicates paths result from calculating spur paths of nodes in the root of $A^{k}$ . For instance, $A^{k}$ deviates from $A^{k-1}$ at some node $(i)$ . Any spur path, ${S^{k}}_{j}$ where $j=0,\ldots ,i$ , that is calculated will be a duplicate because they have already been calculated during the $k-1$ iteration. Therefore, only spur paths for nodes that were on the spur path of $A^{k-1}$ must be calculated, i.e. only ${S^{k}}_{h}$ where $h$ ranges from $(i+1)^{k-1}$ to $(Q_{k})^{k-1}$ . To perform this operation for $A^{k}$ , a record is needed to identify the node where $A^{k-1}$ branched from $A^{k-2}$ .