为什么使用Dijkstraalgorithm，如果广度优先search（BFS）可以更快地做同样的事情？

两者都可以用来find单一来源的最短path。 BFS运行在O（E + V），而Dijkstra运行在O（（V + E）* log（V））。

另外，我见过Dijkstra在路由协议中使用了很多。

因此，为什么使用Dijkstraalgorithm，如果BFS可以更快地做同样的事情呢？

Dijkstra允许为每个步骤分配1以外的距离。例如，在路由中，距离（或权重）可以通过速度，成本，偏好等来分配。algorithm然后给出从源到经过的图中的每个节点的最短path。

与此同时，BFS基本上只是在每次迭代时通过一个“步骤”（链接，边缘，无论您想要在应用程序中调用它）来扩展search，这恰好具有寻find达任何步骤所需的最小步骤的效果给定节点从您的源（“根”）。

如果考虑旅游网站，那么由于节点上的权重（距离），使用Dijkstra的algorithm。

如果您考虑所有节点之间的距离相同，那么BFS是更好的select。

例如，考虑由A->B = 10， A->C = 20， B->F = C->F = 5给出的边权重的A->B A -> (B, C) -> (F)

在这里，如果我们应用BFS，答案将是ABF或ACF，因为两者都是最短path（相对于边的数量），但是如果我们应用Dijstra的话，答案将仅仅是ABF，因为它考虑了连接上的权重path。