Yen's algorithm

In graph theory, Yen's algorithm computes single-source K-shortest loopless paths for a graph with non-negative edge cost.

[2] The algorithm can be broken down into two parts: determining the first k-shortest path,

will hold the k-shortest path, whereas the container

will hold the potential k-shortest paths.

iteration can be divided into two processes: finding all the deviations

and choosing a minimum length path to become

The first process can be further subdivided into three operations: choosing the

Then, if a path is found, the cost of edge

Next, the edges that were removed, i.e. had their cost set to infinity, are restored to their initial values.

The second process determines a suitable path for

Dijkstra's algorithm is used to calculate the best path from

becomes the spur node with a root path of itself,

Dijkstra's algorithm is used to compute the spur path

Dijkstra's algorithm is used to compute the spur path

becomes the spur node with a root path,

Dijkstra's algorithm is used to compute the spur path

This process is continued to the 3rd k-shortest path.

However, within this 3rd iteration, note that some spur paths do not exist.

To store the edges of the graph, the shortest path list

, and the potential shortest path list

Dijkstra's algorithm has a worse case time complexity of

calls to the Dijkstra in computing the spur paths, where

In a condensed graph, the expected value of

[4] Yen's algorithm can be improved by using a heap to store

, the set of potential k-shortest paths.

Using a heap instead of a list will improve the performance of the algorithm, but not the complexity.

[5] One method to slightly decrease complexity is to skip the nodes where there are non-existent spur paths.

paths of minimum length, in reference to those in container

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.

, a record is needed to identify the node where