问求解k条最短路径的Eppstein算法和Yen算法

EN

首先，让我为您提供您所讨论的论文的链接。

埃普斯坦的论文：D. Eppstein, “Finding the k shortest paths,” SIAM J. Comput., vol. 28, no. 2, pp.652–673, Feb. 1999

Yen的论文：J. Y. Yen, “Finding the K Shortest Loopless Paths in a Network,” Management Science, vol. 17, no. 11, pp. 712–716, 1971.

以下是我对Yen算法的解释：

Yen的算法使用两个列表，即列表A(从源到目的地的永久最短路径-按时间顺序排序)和列表B(暂定/候选最短路径)。首先，您必须使用任何合适的最短路径算法(例如Dijkstra)找到从源到目的地的第一个最短路径。然后Yen利用了这样的想法，即第k条最短路径可以共享来自(k-1)-th最短路径的边和子路径(从源到路由内任何中间节点的路径)。然后，你必须选择第(k-1)条最短路径，并依次使路由中的每个节点不可达，即擦掉通往路由中节点的特定边。一旦无法到达该节点，就找到从前面的节点到目的地的最短路径。然后，您有了一个新的路由，它是通过添加公共子路径(从源到不可达节点的前一个节点)创建的，并添加了从前一个节点到目的地的新的最短路径。然后将此路由添加到列表B中，前提是它以前没有出现在列表A或列表B中。在对路由中的所有节点重复此过程后，您必须在列表B中找到最短路径，并将其移动到列表A。您只需重复此过程即可获得K的数量。

该算法的计算复杂度为O(kn^3)。有关更多详细信息，请阅读论文。

算法如下：

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

不幸的是，我没有使用Eppstein的算法，因为Yen的算法对我的问题是最优的。

希望这能有所帮助。干杯。

=====

编辑：

也请看一下wikipedia entry。它有一个很好的例子。

=====

编辑：

我在C中找到了一些实现，链接如下：

Eppstein implementation和Loading Graph for Eppstein。

如果你感兴趣，这里有一个Eppstein的lazy version。链接如下：

Lazy Eppstein by Jimenez and Marzal

=====

编辑：

只是另一个link。其中包含几个实现(C/C++)。

=====

编辑：

我找到了一个Eppstein算法的good explanation。