Eppstein's algorithm and Yen's algorithm for k shortest paths

Question

I'm trying to understand exactly how these algorithms work, but I have been unable to find a simple explanation. I would greatly appreciate it if someone could provide or point me to a description of these algorithms that is easier to understand than the description in the original papers. Thanks.

Answer 1

First of all let me provide you with the links to the papers you were talking about.

Eppstein's paper: D. Eppstein, “Finding the k shortest paths,” SIAM J. Comput., vol. 28, no. 2, pp.652–673, Feb. 1999

Yen's paper: J. Y. Yen, “Finding the K Shortest Loopless Paths in a Network,” Management Science, vol. 17, no. 11, pp. 712–716, 1971.

Here is my explanation of Yen's algorithm:

Yen's algorithm uses two lists, i.e. list A (permanent shortest paths from source to destination - chronologically ordered) and list B (tentative/candidate shortest paths). At first you have to find the 1st shortest path from the source to destination using any well-suited shortest path algorithm (e.g. Dijkstra). Then Yen exploits the idea that the k-th shortest paths may share edges and sub-paths (path from source to any intermediary nodes within the route) from (k-1)-th shortest path. Then you have to take (k-1)th shortest path and make each node in the route unreachable in turn, i.e. rub off particular edge that goes to the node within the route. Once the node is unreachable, find the shortest path from the preceding node to the destination. Then you have a new route which is created by appending the common sub-path (from source to the preceding node of the unreachable node) and adds the new shortest path from preceding node to destination. This route is then added to the list B, provided that it has not appeared in list A or list B before. After repeating this for all nodes in the route, you have to find the shortest route in list B and move that to list A. You just have to repeat this process for number of Ks you have.

This algorithm has a computational complexity of O(kn^3). Please read the paper for more details.

The algorithm is as follows:

G = Adjacent Matrix of the Network
Initialize:
A_1 = shortest-path from source to destination
Glocal ← Local copy of G
for k = 2 → K do
 for i = 1 → [len(A_(k−1) ) − 1] do
  Current Node ← A_(k−1) [i]
  Ri ← Sub-path (root) from source till current node in A_(k−1)
  for j = 1 → k − 1 do
   Rj ← Sub-path (root) from source till current node in A_j
   if Ri == Rj then
    Next Node ← Aj [i+1]
    Glocal(Current Node, Next Node) ← infinity
    Current Node ← unreachable
   end if
  end for
  Si ← Shortest-path from current node till destination
  Bi ← Ri + Si
 end for 
 A_k ← Shortest-path amongst all paths in B
 Restore original graph: Glocal ← Local copy of G
end for

Unfortunately, I have not used Eppstein's one as Yen's algorithm was optimal for my problem.

Hope this helps. Cheers.

=====

Edit:

Please have a look at the wikipedia entry as well. It has a nice example.

=====

Edit:

I have found some implementations in C. The links are as follows:

Eppstein implementation and Loading Graph for Eppstein.

If you are interested, there is a lazy version of Eppstein. The link is as follows:

Lazy Eppstein by Jimenez and Marzal

=====

Edit:

Just another link. This one contains several implementations (C/C++).

=====

Edit:

I have found a good explanation of Eppstein's algorithm.