algorithm - 蛮力 BFS 与 Dijkstra 最短路径算法的运行时间分析

Question

Dijkstra 的运行时间为 O(|E| + |V|log|V|)蛮力 BFS 的运行时间为 O(|E| + |V|)

那么为什么 dijkstra 的更优？看起来它的运行时间更长。

编辑:请查看标记的答案。事实证明，我在加权图(基本上是蛮力)上使用 BFS 对最短路径的运行时间分析是不正确的。在加权图上使用强力 BFS 的上限为 O(V!)。 Dijstra 的更优。

Answer 1

Dijkstra 的运行时间为 O(|E| + |V|log|V|) 但它可以在加权 中找到源节点和目标节点之间的最短路径> 图。 BFS 的运行时间为 O(|E| + |V|)，但它只会在所有边具有相等权重 时找到源节点和目标节点之间的最短路径。如果你所有的边都具有相同的权重，那么确实不需要运行 Dijkstra。