11

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

4

1 回答 1

20

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

Eppstein 的论文：D. Eppstein，“寻找 k 条最短路径”，SIAM J. Comput.，第一卷。28，没有。2，第 652-673 页，1999 年 2 月

Yen 的论文：JY Yen，“寻找网络中的 K 个最短无环路径”，管理科学，卷。17，没有。11，第 712-716 页，1971 年。

以下是我对日元算法的解释：

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 的算法最适合我的问题。

希望这可以帮助。干杯。

=====

编辑：

请同时查看维基百科条目。它有一个很好的例子。

=====

编辑：

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

Eppstein 实施和 Eppstein加载图。

如果你有兴趣，这里有 Eppstein 的懒惰版本。链接如下：

希门尼斯和马扎尔的懒惰爱普斯坦

=====

编辑：

只是另一个链接。这一个包含几个实现（C/C++）。

=====

编辑：

我找到了对 Eppstein 算法的一个很好的解释。

于 2012-12-26T00:43:39.273 回答