Eppstein的算法和日元的算法对于k的最短路径 [英] Eppstein's algorithm and Yen's algorithm for k shortest paths

问题描述

我想正是这些算法是如何工作的理解，但我一直无法找到一个简单的解释。我将非常AP preciate，如果有人可以提供或指向我的这些算法更易于理解比原始论文的描述说明。谢谢你。

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.

推荐答案

首先让我为你提供你在谈论的文件的链接。

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

Eppstein的造纸：<一href="https://www.google.co.uk/url?sa=t&rct=j&q=&esrc=s&source=web&cd=4&ved=0CFEQFjAD&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.39.3901%26rep%3Drep1%26type%3Dpdf&ei=uxXaUKzoL8Kb0QWCyYGoCg&usg=AFQjCNHvBqtdj-r_oGwaHFZJgNyLk4jMbw&sig2=w6nNVkoB9qlR0CiwsCrVWw&bvm=bv.1355534169,d.d2k">D. Eppstein的，寻找第k最短路径，SIAM J. COMPUT，第一卷。 28，没有。 2，pp.652-673，1999年2月

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

甄子丹的文章： J. Y.日元，寻找在K最短无环路径在网络中，管理 科学，第17，没有。 11，第712-716，1971年

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:

甄子丹的算法使用两个列表，即名单A（永久最短路径从源到目的地 - 时间顺序排列）和名单B（暂定/候选最短路径）。首先，你必须找到使用任何非常适合最短路径算法（如Dijkstra算法）的源到目的地的第一个最短路径。然后颜利用了想法，即第k最短路径可以共享边缘和子路径（从源路径的路径内的任何中间节点）从（K-1）个最短路径。然后，你必须采取（K-1）的最短路径，并在路由可达依次在每个节点上，即擦掉那去的路线内的节点特定的优势。一旦节点无法访问，发现从preceding节点到目的的最短路径。然后，你必须是通过附加公共子路径（从源到无法访问的节点的preceding节点）中创建并添加到目的地从preceding节点的新的最短路径的新路线。这条路线，然后添加到列表B，只要它没有出现在列表A或B名单之前。重复这个在路线上的所有节点后，你必须要找到名单B的最短路线，并谨列出答：您只需要重复这个过程，你必须Ks的数量。

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.

该算法具有计算的O（KN ^ 3）的复杂性。请阅读本文了解更多详情。

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

的算法如下：

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的的一个作为甄子丹的算法是最适合我的问题。

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

希望这有助于。干杯。

Hope this helps. Cheers.

=====

编辑：

请看看在维基百科条目的为好。它有一个很好的例子。

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

=====

编辑：

我已经发现在C一些实施该链接如下：

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

Eppstein的实施并 加载图形的Eppstein的。

如果你有兴趣，有一个懒版本。链路如下：

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

懒Eppstein的由希门尼斯和Marzal

=====

编辑：

又一个链接。这其中包含几个实现（C / C ++）。

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

=====

编辑：

我已经找到了很好的解释。

这篇关于Eppstein的算法和日元的算法对于k的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！