有比Dijkstra更快的算法吗？

Question

给定一个只有正边缘重量的定向，连接的图形，是否有比使用斐波那契堆的dijkstra更快地找到两个顶点之间的最短路径的算法？

Wikipedia说，Dijkstra在O（| e | + | v | * log（| v |））（使用fibonacci Heap）中。

我不是在寻找例如执行时间一半的优化，而是在不同时间复杂性的算法（例如从o（n * log n）到o（n））。

此外，我想知道您对以下方法的看法：

1. 确定所有边缘权重的GCD。
2. 将图形转换为具有均匀边缘权重的图。
3. 使用BFS找到两个给定顶点之间的最短路径。

点2的示例：
想象GCD为1。然后我会改变边缘
a ---> b（边缘重量3）
进入
a-> a' - > a'' - > b（边缘重量1）
这种转变会花费恒定的时间，并且必须为每个优势完成一次。因此，我希望该算法在O（| e |）（转换） + O（| e | + | v |）（bfs）= o（2 * | e | + | v |）= o（| e | | + | V |）

感谢您抽出宝贵的时间阅读我的问题，希望不要浪费您的时间^^。祝你今天过得愉快。

Answer 1

您为算法所做的大型OH分析深处存在缺陷。假设所有边缘都是质数。新图中的边缘数将等于所有权重的总和。因此 O(|E| + |V|) 的 新的 图实际上是 O(W x |E| + |V|) 在原始图中可能比 O(|E| + |V| log |V|).

Answer 2

有比Dijkstra更快的算法吗？

是的。这个问题不合格，因此在所有情况下，甚至在大多数情况下都需要更好的性能。在单个情况下具有更好性能的算法足以建立肯定的答案。

尽管Bellman-Ford方法通常比Dijkstra方法需要大量的迭代，但实际上，由于迭代的较小的开销，Bellman-Ford方法可以更高[Golden，B。，1976年。“最短的路径算法：A比较”，《运营研究》，第1卷。 44，第1164-1168页]。

上面的引用来自Dimitri P. Bertsekas（1992年3月）。 “最短路径的简单快速标签校正算法”（PDF）。网络，第1卷。 23，第703-709页，1993年。 http://www.mit.edu/people/dimitrib/slf.pdf. 。检索2008-10-01。

简而言之，我的主张是基于贝特塞卡斯（Bertsekas）对黄金的解释。不管我的结论是否站起来，您都可能发现贝特塞卡（Bertsekas）将其分类为Dijkstra算法为 标签设置 方法，与 标签校正 方法。

Answer 3

有一个具有O（1）的算法：将权重转换为链长，并使用钥匙圈进行节点（实际键环作为口袋中的环）。将钥匙戒指与正确的链连接。选择两个节点，然后将它们彼此拉开。

从一个节点到另一个节点遵循绷紧的链条。这是最短的路径。

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

对于更真实的示例，请使用 蚂蚁菌落优化 在很短的时间内就可以提供非常好的效果。由于您可以在此算法中指定运行次数，因此您可以决定花费多少时间（即运行时仅取决于节点的数量），从而为您提供O（n），但不能保证完美的结果。

Answer 4

总有一个*，它像层次a*和a* jps一样派生。