发现穿过节点的一些任意序列的最短路径？ [英] Finding a shortest path that passes through some arbitrary sequence of nodes?

问题描述

在<一个href="http://stackoverflow.com/questions/7314333/find-shortest-path-from-vertex-u-to-v-passing-through-a-vertex-w">this 的任择议定书前面的问题询问如何找到，它从u到v，并通过一些节点W A图的最短路径。该接受的答案，这是相当不错的，就是运行Dijkstra算法两次 - 一次从u得到w和一次从ω去V本的时间复杂度等于两个调用Dijkstra算法，这是O（M +的n log n）的。

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).

现在考虑一个相关的问题 - 您将得到一个节点序列u ₁ ，U ₂ ，...，U <子> K 和想找到最短路径从u ₁ 为U <子> K 这样的路径通过U <子> 1 ，U _{2 ，...，U <子> K} 的顺序。显然，这可以通过运行Dijkstra算法，一个用于每一对相邻顶点的k-1个实例中，然后连接的最短路径一起进行。这需要时间O（公里+ K N日志N）。或者，你可以使用全对的最短路径算法，像约翰逊的算法来计算所有的最短路径，然后串联适当的最短路径一起O（MN + N ² log n）的时间，这是个好对于k大于n大得多。

Now consider a related question - you are given a sequence of nodes u₁, u₂, ..., u_k and want to find the shortest path from u₁ to u_k such that the path passes through u₁, u₂, ..., u_k 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 + n² log n) time, which is good for k much larger than n.

我的问题是，是否有一个算法来解决这个问题，就是比当k小时以上方法快。有没有这样的算法存在吗？或者被重复Dijkstra的，因为它得到一样好？

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?

推荐答案

而不是运行Dijkstra算法的孤立事例找到路径 U（K） - ＆GT; U（K + 1）一次一个路径，可以一改进Dijkstra状搜索的单个实例被在该序列中的每个节点同时开始，与路径时形成搜索区域满足在-The中间人。

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".

这将有可能减少边的总数走访和减少再穿越边缘相比，制作出一系列的隔离调用Dijkstra算法。

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.

只是一个想法。

编辑：我想我说的是一个双向搜索，以作为有顺序的节点尽可能多的方向 {U（1），U（2），...，U（M）} 。

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)}.

这篇关于发现穿过节点的一些任意序列的最短路径？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！