Dav*_* O. 8 graph-theory dijkstra
给定一个只有正边权重的有向连通图,是否有比使用斐波纳契堆的Dijkstra更快的算法来找到两个顶点之间的最短路径？
维基百科说,Dijkstra在O(| E | + | V |*log(| V |))中(使用斐波纳契堆).
我不是在寻找优化,例如,执行时间的一半,而是具有不同时间复杂度的算法(如从O(n*log n)到O(n)).
此外,我想知道您对以下方法的看法:
第2点的示例:
想象一下GCD为1.然后我将边缘
A ---> B(边缘权重3)
转换为
A-> A' - > A'' - > B(边缘权重1的3倍)
这种转换需要花费不变的时间,并且必须针对每个边缘进行一次.所以我希望这个算法在O(| E |)(变换)+ O(| E | + | V |)(BFS)= O(2*| E | + | V |)= O(| E | + | V |)
感谢您抽出宝贵时间阅读我的问题,希望不要浪费你的时间^^.祝你今天愉快.
Meh*_*ari 10
你为你的算法做的大分析是非常有缺陷的.假设所有边都是素数.新图中的边数将等于所有权重的总和.因此O(|E| + |V|)所述的新图形实际上是O(W x |E| + |V|)在原始图表可以比大得多O(|E| + |V| log |V|).
有比Dijkstra更快的算法吗？
是.这个问题不合格,因此在所有情况下甚至在大多数情况下都要求更好的性能.在单个案例中具有更好性能的算法足以建立肯定答案.
尽管Bellman-Ford方法对Dijkstra方法所需的迭代次数通常较多,但实际上Bellman-Ford方法可能更优越,因为每次迭代的开销更小[Golden,B.,1976."Shortest-Path Algorithms:A比较,"运筹学,卷.44,pp.1164-1168].
以上引用来自Dimitri P. Bertsekas(1992年3月)."用于最短路径的简单快速标签校正算法"(PDF).网络,卷.23,pp.703-709,1993.http: //www.mit.edu/people/dimitrib/SLF.pdf.检索2008-10-01.
简而言之,我的主张是基于Bertsekas对Golden的解释.无论我的结论是否成立,您可能会发现Bertsekas将Dijkstra算法的分类作为标签设置方法的有趣之处,与标签校正方法形成对比.