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. 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. The algorithm can be broken down into two parts, determining the first k-shortest path, A k {displaystyle A^{k}} , and then determining all other k-shortest paths. It is assumed that the container A {displaystyle A} will hold the k-shortest path, whereas the container B {displaystyle B} , will hold the potential k-shortest paths. To determine A 1 {displaystyle A^{1}} , the shortest path from the source to the sink, any efficient shortest path algorithm can be used. To find the A k {displaystyle A^{k}} , where k {displaystyle k} ranges from 2 {displaystyle 2} to K {displaystyle K} , the algorithm assumes that all paths from A 1 {displaystyle A^{1}} to A k − 1 {displaystyle A^{k-1}} have previously been found. The k {displaystyle k} iteration can be divided into two processes, finding all the deviations A k i {displaystyle {A^{k}}_{i}} and choosing a minimum length path to become A k {displaystyle A^{k}} . Note that in this iteration, i {displaystyle i} ranges from 1 {displaystyle 1} to Q k k {displaystyle {Q^{k}}_{k}} . The first process can be further subdivided into three operations, choosing the R k i {displaystyle {R^{k}}_{i}} , finding S k i {displaystyle {S^{k}}_{i}} , and then adding A k i {displaystyle {A^{k}}_{i}} to the container B {displaystyle B} . The root path, R k i {displaystyle {R^{k}}_{i}} , is chosen by finding the subpath in A k − 1 {displaystyle A^{k-1}} that follows the first i {displaystyle i} nodes of A j {displaystyle A^{j}} , where j {displaystyle j} ranges from 1 {displaystyle 1} to k − 1 {displaystyle k-1} . Then, if a path is found, the cost of edge d i ( i + 1 ) {displaystyle d_{i(i+1)}} of A j {displaystyle A^{j}} is set to infinity. Next, the spur path, S k i {displaystyle {S^{k}}_{i}} , is found by computing the shortest path from the spur node, node i {displaystyle i} , to the sink. The removal of previous used edges from ( i ) {displaystyle (i)} to ( i + 1 ) {displaystyle (i+1)} ensures that the spur path is different. A k i = R k i + S k i {displaystyle {A^{k}}_{i}={R^{k}}_{i}+{S^{k}}_{i}} , the addition of the root path and the spur path, is added to B {displaystyle B} . 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 A k {displaystyle A^{k}} by finding the path in container B {displaystyle B} with the lowest cost. This path is removed from container B {displaystyle B} and inserted into container A {displaystyle A} and the algorithm continues to the next iteration.