有比 Dijkstra 更快的算法吗？
给定一个仅具有正边权重的有向连通图，是否有比使用斐波那契堆的 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|）
感谢您花时间阅读我的问题，我希望没有浪费您的时间^^。祝你今天过得愉快。
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?
Wikipedia says, that Dijkstra is in O(|E| + |V| * log(|V|)) (using a fibonacci heap).
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:
- Determine the GCD of all edge weights.
- Transform the graph into a graph with uniform edge weights.
- Use BFS to find the shortest path between two given vertices.
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
您对算法所做的大分析存在严重缺陷。假设所有边都是素数。新图中的边数将等于所有权重的总和。因此，新图的
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 actuallyO(W x |E| + |V|)in the original graph which can be much larger thanO(|E| + |V| log |V|).是的。该问题不符合要求在所有情况下甚至在大多数情况下都具有更好的性能。在单一情况下具有更好性能的算法足以建立肯定的答案。
上面的引文来自 Dimitri P. Bertsekas（1992 年 3 月）。 “一种简单快速的最短路径标签校正算法”(PDF)。网络，卷。 23，第 703-709 页，1993 年。 http://www.mit.edu/people /dimitrib/SLF.pdf。检索于 2008 年 10 月 1 日。
简而言之，我的主张是基于 Bertsekas 对 Golden 的解释。无论我的结论是否成立，您可能会发现 Bertsekas 很有趣，因为它将 Dijkstra 算法分类为标签设置方法，与标签校正方法相比。
Yes. The question isn't qualified so as to require better performance in all cases, or even in most cases. An algorithm with better performance in a single case is sufficient to establish an affirmative answer.
The quote above is from Dimitri P. Bertsekas (March 1992). "A Simple and Fast Label Correcting Algorithm for Shortest Paths" (PDF). Networks, Vol. 23, pp. 703-709, 1993. http://www.mit.edu/people/dimitrib/SLF.pdf. Retrieved 2008-10-01.
In short, my claim is based on Bertsekas' interpretation of Golden. Whether my conclusion stands up or not, you may find Bertsekas interesting for its classification of the Dijkstra algorithm as a label setting method, as contrasted with label correcting methods.
有一种算法的复杂度为 O(1)：将权重转换为链长度，并使用密钥环作为节点（真正的密钥环就像你口袋里的密钥环）。将钥匙圈与正确的链条连接起来。选择两个节点并将它们相互拉开。
沿着拉紧的链条从一个节点到另一个节点。这是最短路径。
要将其实现为计算机程序，您需要两个工业机器人:)
对于更真实的示例，请使用 蚁群优化在短时间内给出了非常好的结果。由于您可以指定该算法中的运行次数，因此您可以决定它花费了多少时间（即运行时间仅取决于节点数量），这为您提供了 O(n) 但不能保证完美的结果。
There is an algorithm which has O(1): Turn the weights into chain lengths and use key rings for nodes (real key rings as those in your pocket). Connect the key rings with the right chains. Select the two nodes and pull them away from each other.
Follow the taut chains from one node to the other. This is the shortest path.
To implement this as a computer program, you'll need two industrial robots :)
For a more real world example, use the Ant colony optimization which gives very good results in a short time. Since you can specify the number of runs in this algorithm, you can decide how much time it spent (i.e. the runtime is only dependent on the number of nodes) which gives you O(n) but not a guaranteed perfect result.
总有 A*，它的衍生物如分层 A* 和 A* JPS。
There's always A*, and it's derivates like Hierarchical A* and A* JPS.