algorithm - 用于在未加权有向图中查找两个节点之间的最短路径的最有效(Big O)算法

Question

我正在寻找最有效的算法，根据大 O 表示法，在未加权的有向图中找到两个节点之间的最短路径。

我主要分为 Dijkstra 的堆和呼吸优先搜索，如果图形被加权，我通常会使用堆。

未加权的图是否会使 Dijkstra 在这种情况下的使用效率低于 BFS？

Answer 1

根据 Wikipedia ,

单源最短路径

• BFS - O(V + E)
• Dijkstra(带列表)- O(V²)
• Dijkstra(修改后的二叉堆)- O((E+V)logV)
• Dijkstra(使用 Fibonacci 堆)- O(E + VlogV) - Fredman 和 Tarjan 实现
• Dijkstra(使用 Fibonacci 堆)- O(EloglogV) - Johnson、Karlsson 和 Poblete 实现

A* 的时间复杂度取决于启发式算法。在无界搜索空间的最坏情况下，扩展的节点数在解决方案的深度(最短路径)d:O(b^d)，其中 b 是分支因子(每个状态的平均后继数)。

选择最适合你的。