给定一个只有正边权重的有向连通图，是否有比使用斐波那契堆的 Dijkstra 更快的算法来找到两个顶点之间的最短路径？
维基百科说，Dijkstra 在 O(|E| + |V| * log(|V|)) 中（使用斐波那契堆）。
我不是在寻找例如一半执行时间的优化，而是在不同时间复杂度的算法（比如从 O(n * log n) 到 O(n)）。
此外，我想知道您对以下方法的看法：
第 2 点的示例：
想象 GCD 为 1。然后我将边缘
A--->B（边缘权重 3）
转换为
A->A'->A''->B（3 倍边缘权重 1）
这种转换需要固定的时间，并且必须为每条边完成一次。所以我希望这个算法在 O(|E|) (transformation) + O(|E| + |V|) (BFS) = O(2 * |E| + |V|) = O(|E|) + |V|)
感谢您花时间阅读我的问题，我希望没有浪费您的时间^^。祝你今天过得愉快。
您为算法所做的大哦分析存在严重缺陷。假设所有边都是素数。新图中的边数将等于所有权重的总和。因此O(|E| + |V|)，新图实际上O(W x |E| + |V|)在原始图中，它可以比 大得多O(|E| + |V| log |V|)。
有比 Dijkstra 更快的算法吗？
是的。这个问题没有资格要求在所有情况下，甚至在大多数情况下都有更好的性能。在单个情况下具有更好性能的算法足以建立肯定的答案。
尽管与 Dijkstra 方法相比，Bellman-Ford 方法通常需要更多的迭代次数，但实际上，Bellman-Ford 方法可能更好，因为每次迭代的开销较小 [Golden, B., 1976。“最短路径算法：A比较，”运筹学，卷。44，第 1164-1168 页]。
上面的引述来自 Dimitri P. Bertsekas（1992 年 3 月）。“一种简单快速的最短路径标签校正算法”（PDF）。网络，卷。23，第 703-709 页，1993。http: //www.mit.edu/people/dimitrib/SLF.pdf。检索于 2008 年 10 月 1 日。
简而言之，我的主张是基于 Bertsekas 对 Golden 的解释。无论我的结论是否成立，您可能会发现 Bertsekas 将 Dijkstra 算法分类为标签设置方法很有趣，与标签校正方法相比。
有一种算法具有 O(1)：将权重转换为链长度，并为节点使用钥匙环（真正的钥匙环就像你口袋里的钥匙环）。用正确的链子连接钥匙圈。选择两个节点并将它们拉开。
沿着从一个节点到另一个节点的紧链。这是最短路径。
要将其实现为计算机程序，您需要两个工业机器人 :)
对于更真实的示例，请使用蚁群优化，它可以在短时间内给出非常好的结果。由于您可以在此算法中指定运行次数，因此您可以决定它花费了多少时间（即运行时间仅取决于节点的数量），这会给您 O(n) 但不能保证完美的结果。
总是有 A*，它是 Hierarchical A* 和 A* JPS 之类的派生词。