有没有比Dijkstra更快的算法？ [英] Are there faster algorithms than Dijkstra?
问题描述
给定一个仅具有正边权重的有向连通图，是否有比使用斐波那契堆的Dijkstra更快的算法来找到两个顶点之间的最短路径？
Given a directed, connected graph with only positive edge weights, are there faster algorithms for finding the shortest path between two vertices, than Dijkstra using a fibonacci heap?
维基百科说，Dijkstra在O（| E | + | V | * log（| V |））中（使用斐波那契堆）。
Wikipedia says, that Dijkstra is in O(|E| + |V| * log(|V|)) (using a fibonacci heap).
我不是寻找优化，例如执行时间的一半，而是时间复杂度不同的算法（例如从O（n * log n）到O（n））。
I'm not looking for optimizations that, for example, half the execution time, but rather algorithms that are in a different time complexity (like going from O(n * log n) to O(n)).
此外，我想了解您对以下方法的看法：
Further, I would like to know your opinion on the following approach:
- 确定所有边缘权重的GCD。
- 将图转换为具有均匀边权的图。
- 使用BFS查找两个给定顶点之间的最短路径。
第2点的示例：
假设GCD为1。然后将edge
A ---> B（边缘重量3）
进入
A-> A'-> A''-> B （3天mes边缘权重1）
此转换花费固定的时间，并且每个边缘都必须执行一次。因此，我希望此算法位于O（| E |）（转换）+ O（| E | + | V |）（BFS）= O（2 * | E | + | V |）= O（| E | + | V |）
Example for point 2:
Imagine the GCD to be 1. Then I would transform the edge
A--->B (edge weight 3)
into
A->A'->A''->B (3 times edge weight 1)
This transformation costs constant time and would have to be done once for every edge. So I expect this algorithm to be in O(|E|) (transformation) + O(|E| + |V|) (BFS) = O(2 * |E| + |V|) = O(|E| + |V|)
感谢您抽出宝贵的时间阅读我的问题，希望您的时间不花时间^^。祝您有美好的一天。
Thanks for taking the time to read my question and I hope not having waisted your time^^. Have a nice day.
推荐答案
您对算法所做的大型分析有很大缺陷。假设所有边都是质数。新图形中的边数将等于所有权重的总和。因此， new 图的 O（| E | + | V |）实际上是 O（W x | E | + | V |）可能比 O（| E | + | V | log | V |）大得多。
The big oh analysis you did for your algorithm is deeply flawed. Assume all edges are prime numbers. The number of edges in the new graph will be equal to sum of all weights. Thus O(|E| + |V|) of the new graph is actually O(W x |E| + |V|) in the original graph which can be much larger than O(|E| + |V| log |V|).
这篇关于有没有比Dijkstra更快的算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
