tem*_*def 17 algorithm graph dijkstra shortest-path graph-algorithm
在此早期的问题中,OP询问如何在图中找到从u到v的最短路径,并且还通过某个节点w.接受的答案非常好,就是运行Dijkstra算法两次 - 一次从u到w,一次从w到v.这时间复杂度等于两次调用Dijkstra算法,即O(m + n log n).
现在考虑一个相关的问题 - 给你一个节点序列u 1,u 2,...,u k,并想找到从u 1到u k的最短路径,使路径通过u 1,u 2, ...,U ķ秩序.显然,这可以通过运行Dijkstra算法的k-1个实例来完成,每个相邻顶点对应一个,然后将最短路径连接在一起.这需要时间O(km + kn log n).或者,您可以使用像Johnson算法这样的全对最短路径算法来计算所有最短路径,然后在O(mn + n 2 log n)时间内将适当的最短路径连接在一起,这对于比n大得多的k是有利的.
我的问题是,当k很小时,是否有一种解决这个问题的算法比上述方法更快.这样的算法存在吗？或者迭代Dijkstra's得到了它的好处？
不是运行 Dijkstra 算法的孤立实例来u(k) -> u(k+1)一次查找一条路径，而是可以在序列中的每个节点同时启动修改后的类似 Dijkstra 搜索的单个实例，并在搜索区域满足“in-”时形成路径。中间”。
与对 Dijkstra 算法进行一系列孤立的调用相比，这可能会减少访问的边总数并减少边的重新遍历。
一个简单的例子是找到两个节点之间的路径。扩展两个节点的搜索区域比仅扩展一个节点的搜索区域要好。在均匀图的情况下，第二个选项将给出半径等于节点之间距离的搜索区域，第一个选项将给出半径一半的两个区域 - 较小的总体搜索区域。
只是一个想法。
编辑：我想我正在谈论双向搜索的多向变体，其方向与序列中的节点一样多{u(1), u(2), ..., u(m)}。