在this earlier question中，OP询问如何在图中找到从u到v的最短路径，并且还通过某个节点w . 接受的答案非常好，就是运行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算法，即O（m n log n） .
现在考虑一个相关的问题 - 给你一个节点序列u1，u2，...，uk，并想找到从u1到uk的最短路径，这样路径就会按顺序通过u1，u2，...，uk . 显然，这可以通过运行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'算法的k-1个实例来计算所有最短路径，然后在O（mn n2 log n）时间内将适当的最短路径连接在一起，这对于比n大得多的k是有利的 .
我的问题是，当k很小时，是否有一种解决这个问题的算法比上述方法更快 . 这样的算法存在吗？或者是Dijkstra的迭代次数是多少？
4 回答
不是运行Dijkstra算法的孤立实例来一次找到一条路径，而是可以同时在序列中的每个节点处开始修改Dijkstra类似搜索的单个实例，并且当搜索区域满足"in-the-middle"时形成路径 .
与对Dijkstra算法进行一系列隔离调用相比，这可能会减少所访问边的总数并减少边的重新遍历 .
一个简单的例子是找到两个节点之间的路径 . 最好扩展关于两个节点的搜索区域，而不仅仅是扩展一个节点 . 在均匀图形的情况下，第二个选项将给出半径等于节点之间距离的搜索区域，第一个选项将给出半径半径的两个区域 - 更少的整体搜索区域 .
只是一个想法 .
编辑：我想我正在谈论bi-directional search的多方向变体，其方向与序列
{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应用大约一半的次数 . 注意复杂性，这与原始解决方案相同 .
从分而治之的角度看你的问题，给定具有n个节点的图G，其中k [1 <= k <= n]我们想要从1-k（i1，i2，... ，我知道），
假设f（j）是从i1到ij的最短路径 . 这个问题很好地细分（你已经看到了它的去向）到较小的寻找最短路径的实例，最终变成f（j）的总和，当j从1变为k . 因此，您的问题受到Djikstra算法的k-1次迭代的最小限制 . 改进它的唯一方法是找到比Djikstra更快的算法来发现2点之间的最短路径 .
至少这是我的看法 . /研究生
通过一次调用Dijkstra算法，您可以获得图中从一个顶点到另一个顶点的最短路径 . 因此，您只需要搜索每个唯一的起始顶点，因此重复的顶点不会使问题更难 .