有比Dijkstra更快的算法吗？

Question

给定一个只有正边权重的有向连通图，是否有比使用Fibonacci堆的Dijkstra算法更快地找到两个顶点之间的最短路径的算法？

维基百科说，Dijkstra算法的时间复杂度是O(|E| + |V| * log(|V|))（使用Fibonacci堆）。

我不是在寻找像将执行时间减半这样的优化，而是寻找时间复杂度不同的算法（例如从O(n*log n)到O(n)）。

此外，我想了解以下方法的您的看法：

1. 确定所有边权的最大公因数。 2. 将图转换为具有统一边权的图。 3. 使用BFS找到两个给定顶点之间的最短路径。

例如，假设最大公因数为1。那么我会将边A--->B（边权为3）转换为A->A'->A''->B（3倍的边权为1）。这个转换需要恒定的时间，并且必须对每个边都进行一次。所以我希望该算法的时间复杂度为O(|E|)（转换）+ O(|E| + |V|)（BFS）= O(2 * |E| + |V|) = O(|E| + |V|)。

感谢您抽出时间阅读我的问题，希望没有浪费您的时间^^。祝您有愉快的一天。

- Dave O.

---

我认为你忘记考虑最大公约数的成本了。 - R. Martinho Fernandes

转换不在恒定时间内运行。您将需要创建可变数量的新顶点。 - R. Martinho Fernandes

最好使用GCD，但是如果需要的话，可以始终退而使用1，以便不浪费步骤1的时间。 - Dave O.

Answer 1

你对算法进行的大O分析是有严重缺陷的。假设所有边都是质数，那么新图中的边数将等于所有权重的总和。因此，在原来的图中，O(|E| + |V|) 的新图实际上是 O(W x |E| + |V|) 的，它可能比O(|E| + |V| log |V|) 大得多。

- Mehrdad Afshari

---

你说得对。在最坏的情况下，所有边权都是质数且图形完整。因此，W 至少为 |V|^2（|V|^2 条边的权重 >= 1）。因此，我的算法至少需要运行 |V|^2 * |V|^2 + |E| = |V|^4 + |E|。然而，我的原始问题仍未得到回答。 - Dave O.

抱歉，我是说|V|^4 + |V| - 为什么我不能编辑我的帖子或评论？ - Dave O.

我不确定是否存在一种针对任意图的渐进更快算法。我所知道的最快算法是使用斐波那契堆的Dijkstra算法。但我无法确定。 - Mehrdad Afshari

Answer 2

有比Dijkstra更快的算法吗？ 是的。问题没有限定要求在所有情况下，甚至大多数情况下都需要更好的性能。在单个情况下具有更好性能的算法足以肯定答案。 尽管Bellman-Ford方法所需迭代次数通常较多，但实践中由于每次迭代的开销较小，Bellman-Ford方法可能更优 [Golden, B., 1976. “Shortest-Path Algorithms: A Comparison,” Operations Research, Vol. 44, pp. 1164-1168]。 上面的引用来自Dimitri P. Bertsekas（1993年），“最短路径的简单且快速的标签修正算法”（PDF）。网络，第23卷，第703-709页。http://www.mit.edu/people/dimitrib/SLF.pdf。检索日期为2008年10月1日。

简而言之，我的论点基于Bertsekas对Golden的解释。无论我的结论是否成立，您可能会发现Bertsekas有趣，因为它将Dijkstra算法分类为“标签设置”方法，与“标签校正”方法形成对比。

- Ewan Todd

---

他特别询问具有较低渐进运行时间复杂度的解决方案。 - Nick Johnson

好的，把它当作通往最终结果的引理来处理。 - Ewan Todd

首先，“实际上”哪个更快的结果并不相关于哪个具有渐近更好的增长，因为在实践中遇到的图形是有限且通常很小的。此外，1976年更快不一定意味着2009年更快。一方面，“实践中”的图形今天更大了——以夸张的例子来说明，对于n=50，“200x^2”比“n^3”快四倍，但对于n=1000，则慢五分之一。 - ShreevatsaR

是的，我明确地关注渐近运行时间。我想知道，如果Dijkstra算法对于这个问题是一个下界，就像n * log n对于排序任意对象一样，在其中定义了一个全序。 - Dave O.

Answer 3

有一个时间复杂度为O(1)的算法：将权重转换为链长，并使用节点的钥匙环（就是口袋里的那种）。用正确的链连接这些钥匙环，选择两个节点并将它们拉开。

从一个节点到另一个节点沿着紧绷的链寻找路径，这就是最短路径。

要将其实现为计算机程序，您需要两个工业机器人 :)

对于更真实的例子，请使用蚁群算法，在短时间内可以得到非常好的结果。由于您可以在此算法中指定运行次数，因此您可以决定它花费的时间（即运行时间仅取决于节点数），这给出了O(n)，但不保证完美结果。

- Aaron Digulla

---

我可以想到一个O(L)算法，其中L是正确解中节点的数量：量子乱序最短路径（http://en.wikipedia.org/wiki/Bogosort#Quantum_Bogosort）。 - R. Martinho Fernandes

如果不考虑图构建步骤，它的时间复杂度是O(1)。 - mouviciel

@Marthinho: 初始设置（不计入）完成后，您只需执行一个简单的操作：将节点分开。好吧，这只是半开玩笑 :) - Aaron Digulla

我认为我可以证明对于任何这样的算法，其下限为O(L)。 - R. Martinho Fernandes

@Aaron，无论如何，你的资源消耗仍然比我的少（两个工业机器人 vs 毁灭几个宇宙）。 - R. Martinho Fernandes

Answer 4

总会有A*算法，以及类似的分层A*和A* JPS等变体。

- Puppy

---

我认为A*算法依赖于某种有意义的启发式方法，用于确定可能是最佳路径的方向。 - mwfearnley