有比Dijkstra更快的算法吗?

你为你的算法做的大oh分析有严重缺陷。假设所有边都是素数。新图形中的边数将等于所有权重之和。因此 O(|E| + |V|) 的 图形实际上是 O(W x |E| + |V|) 在原始图形中,可以比 O(|E| + |V| log |V|) .

有比Dijkstra更快的算法吗?

尽管 Bellman-Ford方法优于Dijkstras方法,实际上Bellman-Ford方法可以

上面的引文来自Dimitri P。贝尔塞卡斯(1992年3月)。”一种简单快速的最短路径标签校正算法(PDF)。《网络》,第23卷,第703-709页,1993年。 http://www.mit.edu/people/dimitrib/SLF.pdf . 检索日期:2008-10-01。

简言之,我的主张是基于贝尔塞卡斯对黄金的解释。不管我的结论是否站得住脚,你们可能会发现Bertsekas对Dijkstra算法的分类很有趣,因为它是一个 标签设置 方法,与 方法。

有一种算法具有O(1):将权重转换为链长度,并使用关键点环作为节点(实际关键点环与口袋中的关键点环相同)。用右侧链条连接钥匙环。选择两个节点并将它们彼此拉开。

沿着拉紧链从一个节点到另一个节点。这是最短的路径。

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

Ant colony optimization 在短时间内取得了很好的效果。由于您可以在该算法中指定运行次数,因此您可以决定它所花费的时间(即运行时间仅取决于节点的数量),这将为您提供O(n),但不能保证完美的结果。