Eppstein的算法和Yen的k最短路径算法

Question

我试图准确理解这些算法是如何工作的，但我一直无法找到一个简单的解释。如果有人能提供或指出我对这些算法的描述比原始论文中的描述更容易理解，我将不胜感激。谢谢。

Answer 1

首先，让我为您提供您正在谈论的论文的链接。

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

日元的论文：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）个最短路径共享边缘和子路径（从源到路径内的任何中间节点的路径）的想法。然后你必须采取（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。