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. Algorithm. Description. The algorithm can be broken down into two parts, determining the first k-shortest path, formula_1, and then determining all other "k"-shortest paths. It is assumed that the container formula_2 will hold the "k"-shortest path, whereas the container formula_3, will hold the potential "k"-shortest paths . To determine formula_1, the shortest path from the source to the sink, any efficient shortest path algorithm can be used. To find the formula_5, where formula_6 ranges from formula_7 to formula_8, the algorithm assumes that all paths from formula_1 to formula_10 have previously been found. The formula_6 iteration can be divided into two processes, finding all the deviations formula_12 and choosing a minimum length path to become formula_5. Note that in this iteration, formula_14 ranges from formula_15 to formula_16. The first process can be further subdivided into three operations, choosing the formula_17, finding formula_18, and then adding formula_12 to the  container formula_3. The root path, formula_17, is chosen by finding the subpath in formula_10 that follows the first formula_14 nodes of formula_24, where formula_25 ranges from formula_15 to formula_27. Then, if a path is found, the cost of edge formula_28 of formula_24 is set to infinity. Next, the spur path, formula_18, is found by computing the shortest path from the spur node, node formula_14, to the sink. The removal of previous used edges from formula_32 to formula_33 ensures that the spur path is different. formula_34, the addition of the root path and the spur path, is added to formula_3. 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 formula_5 by finding the path in container formula_3 with the lowest cost. This path is removed from container formula_3 and inserted into container formula_2 and the algorithm continues to the next iteration. 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. Example. The example uses Yen's "K"-Shortest Path Algorithm to compute three paths  from formula_40 to formula_41. Dijkstra's algorithm is used to calculate the best path from formula_40 to formula_41, which is formula_44 with cost 5. This path is appended to container formula_2 and becomes the first "k"-shortest path, formula_1. Node formula_40 of formula_1 becomes the spur node with a root path of itself, formula_49. The edge, formula_50, is removed because it coincides with the root path and a path in container formula_2. Dijkstra's algorithm is used to compute the spur path formula_52, which is formula_53, with a cost of 8. formula_54 is added to container formula_3 as a potential "k"-shortest  path. Node formula_56 of formula_1 becomes the spur node with formula_58. The edge, formula_59, is removed because it coincides with the root path and a path in container formula_2. Dijkstra's algorithm is used to compute the spur path formula_61, which is formula_62, with a cost of 7. formula_63 is added to container formula_3 as a potential "k"-shortest path. Node formula_65 of formula_1 becomes the spur node with a root path, formula_67. The edge, formula_68, is removed because it coincides with the root path and a path in container formula_2. Dijkstra's algorithm is used to compute the spur path  formula_70, which is formula_71, with a cost of 8. formula_72 is added to container formula_3 as a potential "k"-shortest path. Of the three paths in container B, formula_74 is chosen to become formula_75 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 formula_76 is formula_53. Features. Space complexity. To store the edges of the graph, the shortest path list formula_2, and the potential shortest path list formula_3, formula_80 memory addresses are  required. At worse case, the every node in the graph has an edge to every other node in the graph, thus formula_81 addresses are needed. Only formula_82 addresses are need for both list formula_2 and formula_3 because at most only formula_8 paths will be stored, where it is possible for each path to have formula_86 nodes. 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 formula_87, but using a  Fibonacci heap it becomes formula_88, where formula_89 is the amount of edges in the graph. Since Yen's algorithm makes formula_90 calls to the Dijkstra in computing the spur paths, where formula_91 is the length of spur paths. In a condensed graph, the expected value of formula_91 is formula_93, while the worst case is formula_86. , the time complexity becomes formula_95. Improvements. Yen's algorithm can be improved by using a heap to store formula_3, 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. 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 formula_5. Also, if container formula_3 has formula_99 paths of minimum length, in reference to those in container formula_2, then they can be extract and inserted into container formula_2 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 formula_5. For instance, formula_103 deviates from formula_10 at some node formula_32. Any spur path, formula_106 where formula_107, that is calculated will be a duplicate because they have already been calculated during the formula_27 iteration. Therefore, only spur paths for nodes that were on the spur path of formula_10 must be calculated, i.e. only formula_110 where formula_111 ranges from formula_112 to formula_113. To perform this operation for formula_103, a record is needed to identify the node where formula_10  branched from formula_116.