寻找第 k 个最短路径? [英] Finding kth-shortest paths?
问题描述
找到图中两点之间的最短路径是一个经典的算法问题，有很多很好的答案(
第二最短路径 (K=2)
寻找第 2 条最短路径的直觉是采用第 1 条最短路径，但强制"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.
第二次迭代的过程如下所示:
//尝试不使用边 1graph_1 = remove_edge(图，D-E)候选_1 = shortest_1(D, D) + Dijkstra(graph_1, D, F)//尝试不使用边 2graph_2 = remove_edge(graph, E-F)候选_2 = shortest_1(D, E) + Dijkstra(graph_2, E, F)shortest_2 = pick_shortest(candidate_1,Candidate_2)最后，选择新路径中最短的作为第二最短路径.
第三最短路径 (K=3)
正如通过从第 1 条最短路径中删除边来找到第 2 条最短路径一样，通过从第 2 条最短路径中删除边来找到第 3 条最短路径.
然而，这次的新细微差别在于，当我们删除边 DA(shortest_2 中的第一条边)时，我们还想删除边 代码.如果我们不这样做，只去除边DA，那么当我们在graph_3上运行Dijkstra时，我们将再次找到第一条最短路径(DEF)，而不是第三条最短路径！
对于 graph_4 和 graph_5，然而，我们不需要删除任何其他边，因为这些边在使用时不会给我们以前见过的最短路径.
因此，整个过程看起来类似于寻找第二条最短路径，但有细微差别，除了第二条最短路径之外，我们还想删除第一条最短路径中看到的一些边.该决定是根据 shortest_1 和 shortest_2 是否共享通向被移除边的子路径做出的.
//尝试不使用边 1edge_3 = [D-A]如果 shortest_1 和 shortest_2 共享直到节点 D 的子路径://真，因为 shortest_1 和 shortest_2 在最短路径中都有 D//D-E 是从 D 连接的 shortest_1 中的边，因此添加edge_3.add(D-E)graph_3 = remove_edges(图，edges_3)Candidate_3 = shortest_e(D, D) + Dijkstra(graph_3, D, F)//返回无穷大//尝试不使用边 2edge_4 = [A-E]如果 shortest_1 和 shortest_2 共享直到节点 A 的子路径://错误，因为 shortest_1 中没有通过 A 的边//所以没有添加边graph_4 = remove_edges(graph,edges_4)Candidate_4 = shortest_2(D, A) + Dijkstra(graph_4, A, F)//返回无穷大//尝试不使用边 3edge_5 = [E-F]如果 shortest_1 和 shortest_2 共享直到节点 E 的子路径://错误，因为 shortest_1 通过 D-E 而 shortest_2 通过 D-A-E//所以没有添加边graph_5 = remove_edges(graph,edge_5)候选_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 算法的一个很好的解释.
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?
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 and F), we can just run Dijkstra’s algorithm. The entire code for Yen’s algorithm at the first iteration is:
shortest_1 = Dijkstra(graph, D, F)
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 in shortest_1), and then complete the shortest path by running Dijkstra(graph_1, D, F). We combine the shortest path already known from node D to D (which is just the node D itself), with the new shortest path from node D to F. This gives us an alternative path D->F.
Then we try to remove the edge E-F (the second edge in shortest_1), and then complete the shortest path by running Dijkstra(graph_2, E, F). We combine the shortest path already known from node D to E, with the new shortest path from node E to F. This gives us yet another alternative path D->F.
The procedure for the 2nd iteration thus looks like this:
// 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)
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 in shortest_2), we also want to remove edge D-E. If we don’t do this, and remove only the edge D-A, then when we run Dijkstra on graph_3, we will find the 1st shortest path again (D-E-F), instead of the 3rd shortest path!
For graph_4 and graph_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 and shortest_2 share a subpath leading up to the edge which is being removed.
// 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)
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 from graph_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 list B 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 个最短路径?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
