This paper gives a survey on the previous algorithms to find $$k$$ shortest loopless paths in a network and proposed a new one.

# Survey

@techreport{bkh,
title = {An Algorithm (The rh Best Path Algorithm) for Finding and Ranking Paths Through a Network},
author = {F. Bock and H. Kantner and J. Haynes},
institution = {Armour Research Foundation},
month = {Nov 15},
year = 2007,
}


This enumerates all possible paths from the origin to the sink, then sorts from these the K paths that have the shortest lengths.

@article{p,
title = {The kth best route through a network},
author = {M. Pollack},
journal = {Opns. Res.},
volume = 9,
number = 4,
pages = 578,
year = 1961,
}


This finds the $$K$$-th shortest path by first obtaining the $$K-1$$ shortest paths. Then the distance of each arc in each of the 1st, 2nd, …, $$(K-1)$$st shortest paths is set, in turn, to infinity. The shortest-path problem is solved for each such case. The best of these resulting shortest paths is the desired K-th shortest path.

@article{ckr,
title = {Computing the N Best Loopless Paths in a Network},
author = {S. Clarke and A. Krikorian and J. Rausan},
journal = {J. of SIAM},
volume = 11,
number = 4,
pages = {1096--1102},
month = Dec,
year = 1963,
}


This finds the shortest path first, then finds the $$K$$ shortest path from all paths that branch out from the shortest path.

@techreport{s,
title = {The k Shortest Routes and the k Shortest Chains in a Graph},
author = {M. Sakarovitch},
institution = {Opns. Res. Center, University of California, Berkeley},
number = {ORC-32},
month = Oct,
year = 1966,
}


This finds $$H>K$$ shortest paths that may contain loops, then the $$H$$ paths are scanned for the $$K$$ shortest paths that contain no loops.

# Algorithm

The algorithm proposed in this paper is as follows:

A := Shortest path from S to T
for k := 2 to K do
for i := 1 to length(A)-1 do
nodeA = A[k-1].node(i)
for j := 1 to k-2
nodeB = A[j].node(i)
if (nodeA == nodeB) then
distance(nodeA,nodeB) = infinity
endif
endfor
S[i] = The shortest path from nodeA to T according to the current distance values
R[i] = The path in A[k-1] from S to nodeA
B[i] = R[i] + S[i]
endfor
A[k] = min length paths amongst all B[i]
restore distance(nodeA,nodeB) to original value if modified
endfor


## Bibliographic data

@article{
title = "Finding the K Shortest Loopless Paths in a Network",
author = "Jin Y. Yen",
journal = "Management Science",
volume = "17",
number = "11",
series = "Theory Series",
pages = "712--716",
month = "Jul",
year = "1971",
}