找到第k个最短的路径？

Question

找到图中两点之间的最短路径是一个经典的算法问题,有许多好的答案(Dijkstra算法,Bellman-Ford等)我的问题是,是否有一种有效的算法,给定一个有向加权图,一对节点s和t以及值k,找到s和t之间的第k个最短路径.如果有多条相同长度的路径都与第k个最短路径相关,那么算法返回任何路径都是正确的.

我怀疑这个算法可能是在多项式时间内完成的,尽管我知道最长的路径问题可能会减少,这会使NP难以实现.

有没有人知道这样的算法,或者表明它是NP难的减少？

Answer 1

最好的(也是基本上最优的)算法归功于Eppstein.

Answer 2

您正在寻找Yen的算法来寻找K最短路径.然后,k最短路径将是该组中的最后路径.

下面是一个实现日元的算法.

这是描述它的原始论文.

Answer 3

从可用的第 K 个最短路径算法中，Yen 算法是最容易理解的。这主要是因为 Yen 的算法首先需要计算所有 K-1 条最短路径，然后才能计算第 K 条最短路径，因此可以将其分解为子问题。

此外，由于每个子问题都使用标准的最短路径算法（例如Dijkstra 算法），因此它是从第1 条最短路径问题到第K 条最短路径问题的更自然的扩展。

以下是在具有等权边的示例图中查找第三条最短路径的工作原理。

第一最短路径 (K=1)

如果我们正在寻找起点和终点之间的第一条最短路径（这里是D和之间F），我们可以运行 Dijkstra 算法。Yen 算法在第一次迭代时的完整代码是：

shortest_1 = Dijkstra(graph, D, F)

给定一个起始图，这给出了第一条最短路径（K=1）。

第二条最短路径 (K=2)

寻找第二条最短路径的直觉是采用第一条最短路径，但“强制”Dijkstra 算法沿着不同的、略微不太理想的路线。Yen 的算法“强制”Dijkstra 算法沿不同的路线运行的方式是删除属于第一最短路径的边之一。

但是我们移除哪条边以获得下一条最短路径？我们需要尝试一条一条地去除每条边，看看哪条边去除给我们下一条最短路径。

首先我们尝试移除边D-E（ 中的第一条边shortest_1），然后通过运行完成最短路径Dijkstra(graph_1, D, F)。我们将已知的从节点D到D（也就是节点D本身）的最短路径与从节点D到的新最短路径结合起来F。这给了我们一条替代路径D->F。

然后我们尝试去除边E-F（ 中的第二条边shortest_1），然后通过运行 完成最短路径Dijkstra(graph_2, E, F)。我们将已知的从节点D到E的最短路径与从节点E到的新最短路径结合起来F。这为我们提供了另一条替代途径D->F。

因此，第二次迭代的过程如下所示：

// Try without edge 1
graph_1 = remove_edge(graph, D-E)
candidate_1 = shortest_1(D, D) + Dijkstra(graph_1, D, F)

// Try without edge 2
graph_2 = remove_edge(graph, E-F)
candidate_2 = shortest_1(D, E) + Dijkstra(graph_2, E, F)

shortest_2 = pick_shortest(candidate_1, candidate_2)

最后，选择最短的替代新路径作为第二最短路径。

第三条最短路径 (K=3)

正如通过从第 1 条最短路径中删除边来找到第 2 条最短路径一样，通过从第 2 条最短路径中删除边来找到第 3 条最短路径。

然而，这一次的新细微差别是，当我们删除 edge D-A（ 中的第一条边shortest_2）时，我们也想删除 edge D-E。如果我们不这样做，只删除边D-A，那么当我们在 上运行 Dijkstra 时graph_3，我们将再次找到第 1 条最短路径 ( D-E-F)，而不是第 3 条最短路径！

然而，对于graph_4和graph_5，我们不需要删除任何其他边，因为这些边在使用时不会为我们提供以前见过的最短路径。

因此，整个过程看起来类似于寻找第二条最短路径，但有细微差别，除了第二条最短路径之外，我们还想删除第一条最短路径中看到的一些边缘。该决定是基于是否shortest_1和shortest_2共享通向正在被删除的边缘的子路径做出的。

// Try without edge 1
edges_3 = [D-A]
if shortest_1 and shortest_2 share subpath up to node D: 
    // True because both shortest_1 and shortest_2 have D in shortest path
    // D-E is edge in shortest_1 that is connected from D, and so it is added
    edges_3.add(D-E)

graph_3 = remove_edges(graph, edges_3)
candidate_3 = shortest_e(D, D) + Dijkstra(graph_3, D, F) // returns infinity


// Try without edge 2
edges_4 = [A-E]
if shortest_1 and shortest_2 share subpath up to node A:
    // False because there are no edges in shortest_1 that go through A
    // So no edges added

graph_4 = remove_edges(graph, edges_4)
candidate_4 = shortest_2(D, A) + Dijkstra(graph_4, A, F) // returns infinity


// Try without edge 3
edges_5 = [E-F]
if shortest_1 and shortest_2 share subpath up to node E:
    // False because shortest_1 goes through D-E while shortest_2 goes through D-A-E
    // So no edges added

graph_5 = remove_edges(graph, edges_5)
candidate_5 = shortest_2(D, E) + Dijkstra(graph_5, E, F)


shortest_3 = pick_shortest(candidate_2, candidate_3, candidate_4, candidate_5)

请注意，当我们这次选择最短路径时，我们如何考虑迭代 2（即candidate_2）中未使用的候选者，实际上最终选择了从 中找到的最短路径graph_2。同理，在下一次迭代（K=4）中，我们会发现实际上在迭代K=3中找到了第4条最短路径。可以看到，这个算法是提前做功的，所以在寻找第K条最短路径的同时，也在探索超出第K条最短路径的部分路径。因此它不是第 K 个最短路径问题的最佳算法。Eppstein 算法可以做得更好，但更复杂。

上述方法可以通过使用多个嵌套循环来推广。Yen 算法的维基百科页面已经为更通用的实现提供了极好的伪代码，所以我不会在这里写它。请注意，维基百科代码使用一个列表A来保存每条最短路径，并使用一个列表B来保存每条候选路径，并且候选最短路径在循环迭代中持续存在。

评论

由于使用了 Dijkstra 算法，Yen 算法不能有包含循环的第 K 条最短路径。当使用未加权的边时（如上例所示），这并不明显，但如果添加了权重，则可能会发生这种情况。出于这个原因，Eppstein 的算法也能更好地工作，因为它考虑了循环。这个另一个答案包括一个很好的解释 Eppstein 算法的链接。