graph-theory - 有比 Dijkstra 更快的算法吗？

Question

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

维基百科说，Dijkstra 在 O(|E| + |V| * log(|V|)) 中(使用斐波那契堆)。

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

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

确定所有边权重的 GCD。

将图转换为具有统一边权重的图。

使用 BFS 找到两个给定顶点之间的最短路径。

第 2 点的示例:
想象 GCD 为 1。然后我会变换边缘
A--->B(边权重 3)
进入
A->A'->A''->B(边权重 1 的 3 倍)
这种转换需要花费恒定的时间，并且必须对每条边进行一次。所以我希望这个算法在 O(|E|) (transformation) + 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|)大得多的原始图中.