寻找通过任意节点序列的最短路径？
现在考虑一个相关问题 - 给定一个节点序列 u1, u2, ..., uk 并且想要找到从 u1 到 uk 的最短路径，使得该路径经过 u1, u2, 。 .., uk 按顺序。显然，这可以通过运行 Dijkstra 算法的 k-1 个实例来完成，每对相邻顶点一个实例，然后将最短路径连接在一起。这需要时间 O(km + kn log n)。或者，您可以使用全对最短路径算法（如约翰逊算法）来计算所有最短路径，然后在 O(mn + n2 log n) 时间内将适当的最短路径连接在一起，这很好对于 k 远大于 n。
我的问题是，当 k 很小时，是否有一种算法可以比上述方法更快地解决这个问题。这样的算法存在吗？或者迭代迪杰斯特拉算法是否已经达到最佳效果？
In this earlier question the OP asked how to find a shortest path in a graph that goes from u to v and also passes through some node w. The accepted answer, which is quite good, was to run Dijkstra's algorithm twice - once to get from u to w and once to get from w to v. This has time complexity equal to two calls to Dijkstra's algorithm, which is O(m + n log n).
Now consider a related question - you are given a sequence of nodes u1, u2, ..., uk and want to find the shortest path from u1 to uk such that the path passes through u1, u2, ..., uk in order. Clearly this could be done by running k-1 instances of Dijkstra's algorithm, one for each pair of adjacent vertices, then concatenating the shortest paths together. This takes time O(km + k n log n). Alternatively, you could use an all-pairs shortest paths algorithm like Johnson's algorithm to compute all shortest paths, then concatenate the appropriate shortest paths together in O(mn + n2 log n) time, which is good for k much larger than n.
My question is whether there is an algorithm for solving this problem that is faster than the above approaches when k is small. Does such an algorithm exist? Or is iterated Dijkstra's as good as it gets?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
而不是运行 Dijkstra 算法的孤立实例来查找路径
u(k) -> u(k+1)一次一个路径，是否可以在序列中的每个节点同时启动修改后的类似 Dijkstra 搜索的单个实例，并且当搜索区域满足“in-the-”时形成路径中间”。与对 Dijkstra 算法进行一系列孤立的调用相比，这可能会减少访问的边总数并减少边的重新遍历。
一个简单的例子是找到两个节点之间的路径。扩展两个节点的搜索区域比仅扩展一个节点的搜索区域要好。在均匀图的情况下，第二个选项将给出半径等于节点之间距离的搜索区域，第一个选项将给出半径一半的两个区域 - 较小的整体搜索区域。
只是一个想法。
编辑：我想我正在谈论双向搜索的多向变体，具有与序列
{u(1), u(2), ..., u(m)}中的节点一样多的方向。Rather than running isolated instances of Dijkstra's algorithm to find the paths
u(k) -> u(k+1)one path at a time, can a single instance of a modified Dijkstra-like search be started at each node in the sequence simultaneously, with the paths formed when search regions meet "in-the-middle".This would potentially cut down on the total number of edges visited and reduce re-traversal of edges compared to making a series of isolated calls to Dijkstra's algorithm.
An easy example would be finding the path between two nodes. It would be better to expand the search regions about both nodes than just expanding about one. In the case of a uniform graph, the second option would give a search region with radius equal to the distance between the nodes, the first option would give two regions of half the radius - less overall search area.
Just a thought.
EDIT: I guess I'm talking about a multi-directional variant of a bi-directional search, with as many directions as there are nodes in the sequence
{u(1), u(2), ..., u(m)}.我不知道如何才能做得更好，这就是我能想到的。假设图是无向的，从任何节点 u 到节点 v 的最短路径将与从 v 到 u 的最短路径相同（当然相反）。
现在，对于顺序为 u1 u2 u3.. un 的最短路径的情况，我们可以在 u2 上运行 Djikstra 算法（并在一次运行中找到最短路径 u1-u2、u2-u3），然后在 u4 上运行（对于 u3 -u4 和 u4-u5)，然后是 u6.. 等等。这可以将 Djikstra 的涂抹次数减少大约一半。请注意，就复杂性而言，这与原始解决方案相同。
I don't see how we can do too much better, here's all I can think of. Assuming the graph is undirected, the shortest path from any node u to node v would be the same as that from v to u (in reverse of course).
Now, for your case of a shortest path in the order u1 u2 u3.. un, we could run Djikstra's algorithm on u2 (and find the shortest paths u1-u2, u2-u3 in one run), then on u4 (for u3-u4 and u4-u5), then u6.. and so on. This reduces the number of times you apply Djikstra's by roughly a half. Note that complexity wise, this is identical to the original solution.
通过一次调用 Dijkstra 算法，您可以获得图中从一个顶点到所有另一个顶点的最短路径。因此，您只需要搜索每个唯一起始顶点，因此重复的顶点不会使问题变得更加困难。
You get the shortest path from one vertex to all the other in the graph by one call to Dijkstra's algorithm. Thus you only need to do a search for each unique starting vertex so repeated vertices does not make the problem any harder.