相关疑难解决方法(0)

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

维基百科说,Dijkstra在O(| E | + | V |*log(| V |))中(使用斐波纳契堆).

我不是在寻找优化,例如,执行时间的一半,而是具有不同时间复杂度的算法(如从O(n*log n)到O(n)).

此外,我想知道您对以下方法的看法:

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

第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 |)

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