寻找第k条最短路径?
寻找图中两点之间的最短路径是一个经典的算法问题,有很多很好的答案(Dijkstra 算法< /a>, Bellman-Ford 等)我的问题是是否存在一种有效的算法,给定一个有向加权图、一对节点 s 和 t 以及一个值 k,找到s 和 t 之间的第 k 最短路径。如果有多条长度相同的路径都与第 k 最短路径相关,则算法可以返回其中任何一条路径。
我怀疑这个算法可能可以在多项式时间内完成,尽管我知道可能会减少 最长路径问题,这将使它成为NP难题。
有谁知道这样的算法,或者知道它是 NP 困难的简化算法吗?
Finding the shortest path between two points in a graph is a classic algorithms question with many good answers (Dijkstra's algorithm, Bellman-Ford, etc.) My question is whether there is an efficient algorithm that, given a directed, weighted graph, a pair of nodes s and t, and a value k, finds the kth-shortest path between s and t. In the event that there are multiple paths of the same length that all tie for the kth-shortest, it's fine for the algorithm to return any of them.
I suspect that this algorithm can probably be done in polynomial time, though I'm aware that there might be a reduction from the longest path problem that would make it NP-hard.
Does anyone know of such an algorithm, or of a reduction that show that it is NP-hard?
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(4)
您正在寻找 Yen 的算法来查找
K
最短路径。第 k 个最短路径将成为该组中的最后一条路径。以下是 Yen 算法的实现。
这是描述它的原始论文。
You're looking for Yen's algorithm for finding
K
shortest paths. Thek
th shortest path will then be the last path in that set.Here's an implementation of Yen's algorithm.
And here's the original paper describing it.
最好的(基本上是最佳的)算法是由于 艾普斯坦。
The best (and basically optimal) algorithm is due to Eppstein.
从可用的第 K 个最短路径算法中,Yen 的算法是最容易理解的。这主要是因为Yen的算法首先需要计算所有K-1条最短路径,然后才能计算第K条最短路径,因此它可以分解为子问题。
此外,由于每个子问题都使用标准的最短路径算法(例如Dijkstra算法),它是从第一个最短路径问题到第K个最短路径问题的更自然的延伸。
以下是在具有等权边的示例图中查找第三条最短路径的工作原理。
第一条最短路径 (K=1)
如果我们正在寻找起点和目的地之间的第一条最短路径(此处为
D
和F
),我们可以运行 Dijkstra 算法。 Yen 算法在第一次迭代时的完整代码是:给定一个起始图,这给出了第一个最短路径(K=1)。
第二条最短路径 (K=2)
寻找第二条最短路径的直觉是采用第一条最短路径,但“强制”Dijkstra 算法沿着不同的、稍微不同的方向前进。不太理想的路线。 Yen 的算法“迫使”Dijkstra 的算法沿着不同的路线行驶的方式是删除属于第一条最短路径的边之一。
但是我们要删除哪条边才能得到下一条最短路径呢?我们需要尝试一条一条地删除每条边,看看删除哪一条边可以为我们提供下一条最短路径。
首先,我们尝试删除边
DE
(shortest_1
中的第一条边),然后通过运行Dijkstra(graph_1, D、 F)
。我们将已知的从节点D
到D
(这只是节点D
本身)的最短路径与从节点开始的新最短路径结合起来D
到F
。这为我们提供了一条替代路径D->F
。然后我们尝试删除边
EF
(shortest_1
中的第二条边),然后通过运行Dijkstra(graph_2, E, F)< 来完成最短路径/代码>。我们将已知的从节点
D
到E
的最短路径与从节点E
到F
的新最短路径结合起来>。这为我们提供了另一条替代路径D->F
。因此,第二次迭代的过程如下所示:
最后,选择替代新路径中最短的一条作为第二最短路径。
第三条最短路径(K=3)
正如通过从第一条最短路径中删除边来找到第二条最短路径一样,第三条最短路径也是通过从第二条最短路径中删除边来找到第三条最短路径。
不过,这次新的细微差别是,当我们删除边
DA
(shortest_2
中的第一条边)时,我们还想删除边DE.如果我们不这样做,而只删除边
DA
,那么当我们在graph_3
上运行Dijkstra时,我们将再次找到第一条最短路径(DEF
),而不是第三条最短路径!但是,对于
graph_4
和graph_5
,我们不需要删除任何其他边,因为这些边在使用时不会为我们提供之前看到的最短路径。,整个过程看起来与查找第二条最短路径类似,但细微之处在于,除了第二条最短路径之外,我们还希望删除在第一条最短路径中看到的一些边。该决定是根据
shortest_1
和shortest_2
是否共享通向要删除的边的子路径来做出的。请注意,当我们这次选择最短路径时,我们考虑了迭代 2 中未使用的候选路径(即
candidate_2
),并且实际上最终选择了从graph_2
中找到的最短路径。同样的,在下一次迭代(K=4)时,我们会发现第4条最短路径实际上是在迭代K=3时找到的。可以看到,这个算法是提前做工作的,所以它在寻找第K条最短路径的同时,也在探索第K条最短路径之外的一些路径。因此,它不是解决第 K 最短路径问题的最优算法。 Eppstein算法可以做得更好,但更复杂。上述方法可以通过使用多个嵌套循环来推广。 关于 Yen 算法的维基百科页面 已经为更通用的实现提供了出色的伪代码,所以我将不要写在这里。请注意,维基百科代码使用列表
A
来保存每个最短路径,使用列表B
来保存每个候选路径,并且候选最短路径在循环迭代中持续存在。备注
由于使用了Dijkstra算法,Yen算法不可能有第K条包含环路的最短路径。当使用未加权的边时(如上例所示),这种情况并不那么明显,但如果添加权重,则可能会发生这种情况。因此,Eppstein 的算法也效果更好,因为它考虑了循环。 此其他答案包括 链接,对 Eppstein 算法进行了很好的解释。
From the available Kth shortest path algorithms, Yen’s algorithm is the easiest to understand. Mostly this is because Yen’s algorithm first needs to compute all K-1 shortest paths before it can compute the Kth shortest path, so it can be broken down into sub-problems.
Furthermore, since each sub-problem uses a standard shortest path algorithm (e.g. Dijkstra’s algorithm), it is a more natural extension from the 1st shortest path problem to the Kth shortest path problem.
Here is how it works for finding the 3rd shortest path in an example graph with equal-weight edges.
1st shortest path (K=1)
If we are looking for the 1st shortest path between a start and a destination (here, between
D
andF
), we can just run Dijkstra’s algorithm. The entire code for Yen’s algorithm at the first iteration is:Given a starting graph, this gives the 1st shortest path (K=1).
2nd shortest path (K=2)
The intuition for finding the 2nd shortest path is to take the 1st shortest path but “force” Dijkstra’s algorithm along a different, slightly less optimal route. The way Yen’s algorithm “forces” Dijkstra’s algorithm along a different route, is by removing one of the edges that are part of the 1st shortest path.
But which of the edges do we remove to get the next shortest path? We need to try removing each edge, one by one, and see which edge removal gives us the next shortest path.
First we try to remove edge
D-E
(the first edge inshortest_1
), and then complete the shortest path by runningDijkstra(graph_1, D, F)
. We combine the shortest path already known from nodeD
toD
(which is just the nodeD
itself), with the new shortest path from nodeD
toF
. This gives us an alternative pathD->F
.Then we try to remove the edge
E-F
(the second edge inshortest_1
), and then complete the shortest path by runningDijkstra(graph_2, E, F)
. We combine the shortest path already known from nodeD
toE
, with the new shortest path from nodeE
toF
. This gives us yet another alternative pathD->F
.The procedure for the 2nd iteration thus looks like this:
At the end, the shortest of the alternative new paths is chosen as the 2nd shortest path.
3rd shortest path (K=3)
Just as the 2nd shortest path was found by removing edges from the 1st shortest path, the 3rd shortest path is found by removing edges from the 2nd shortest path.
The new nuance this time, however, is that for when we remove edge
D-A
(the first edge inshortest_2
), we also want to remove edgeD-E
. If we don’t do this, and remove only the edgeD-A
, then when we run Dijkstra ongraph_3
, we will find the 1st shortest path again (D-E-F
), instead of the 3rd shortest path!For
graph_4
andgraph_5
, however, we do not need to remove any other edges, since those edges, when used, won’t give us previously seen shortest paths.Thus, the overall procedure looks similar to finding the 2nd shortest path, but with the nuance that we also want to remove some edges seen in the 1st shortest path in addition to the 2nd shortest path. The decision is made based on whether
shortest_1
andshortest_2
share a subpath leading up to the edge which is being removed.Note how when we pick the shortest path this time, we take into account unused candidates from iteration 2 (i.e.
candidate_2
), and actually end up picking the shortest path found fromgraph_2
. In the same way, on the next iteration (K=4), we will find that the 4th shortest path was actually found in iteration K=3. As you can see, this algorithm is doing work in advance, so while it is finding the Kth shortest path, it is also exploring some of the paths beyond the Kth shortest path. It is thus not the most optimal algorithm for the Kth shortest path problem. The Eppstein algorithm can do better, but it is more complex.The above approach can be generalized by using several nested loops. The Wikipedia page on Yen’s algorithm already gives excellent pseudocode for the more generic implementation, so I will refrain from writing it here. Note that the Wikipedia code uses a list
A
to hold each shortest path, and a listB
to hold each candidate path, and that candidate shortest paths persist across loop iterations.Remarks
Due to the use of Dijkstra’s algorithm, Yen’s algorithm cannot have a Kth shortest path that contains a loop. This is not as noticable when un-weighted edges are used (as in the example above), but could occur if weights are added. For this reason, Eppstein’s algorithm works better as well, since it considers loops. This other answer includes a link to a good explanation of Eppstein’s algorithm.
尽管该问题有一个有效的可接受答案,但该答案通过提供示例工作代码解决了实现问题。在这里找到第 k 个最短路径的有效代码:
Even though, the question has a valid accepted answer, this answer addresses the problem of implementation by providing a sample working code. Find the valid code for kth shortest path here: