如果广度优先搜索 (BFS) 可以更快地完成同样的事情，为什么要使用 Dijkstra 算法? [英] Why use Dijkstra's Algorithm if Breadth First Search (BFS) can do the same thing faster?

问题描述

两者都可用于从单个源中找到最短路径.BFS 在 O(E+V) 中运行，而 Dijkstra 在 O((V+E)*log(V)) 中运行.

Both can be used to find the shortest path from single source. BFS runs in O(E+V), while Dijkstra's runs in O((V+E)*log(V)).

此外，我已经看到 Dijkstra 在路由协议中使用了很多类似的方法.

Also, I've seen Dijkstra used a lot like in routing protocols.

因此，如果 BFS 可以更快地完成同样的事情，为什么要使用 Dijkstra 算法?

Thus, why use Dijkstra's algorithm if BFS can do the same thing faster?

推荐答案

Dijkstra 允许为每一步指定 1 以外的距离.例如，在路由中，距离(或权重)可以通过速度、成本、偏好等来分配.然后该算法为您提供从源到遍历图中每个节点的最短路径.

Dijkstra allows assigning distances other than 1 for each step. For example, in routing the distances (or weights) could be assigned by speed, cost, preference, etc. The algorithm then gives you the shortest path from your source to every node in the traversed graph.

与此同时，BFS 基本上只是在每次迭代中将搜索扩展一个步"(链接、边缘，无论您想在应用程序中调用它)，这恰好具有找到最小步数的效果 需要从你的源(root")到达任何给定的节点.

Meanwhile BFS basically just expands the search by one "step" (link, edge, whatever you want to call it in your application) on every iteration, which happens to have the effect of finding the smallest number of steps it takes to get to any given node from your source ("root").

这篇关于如果广度优先搜索 (BFS) 可以更快地完成同样的事情，为什么要使用 Dijkstra 算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！