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

问题描述

两者都可以用来发现从单个源的最短路径。 BFS运行在O（E + V），而Dijkstra的为O（（V + E）*日志（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.

因此​​，为什么要使用Dijkstra算法，如果BFS可以做同样的事情更快？

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

推荐答案

Dijkstra算法允许指定的距离比1的每个步骤等。例如，在路由的距离（或重量）可以通过速度，成本，preference等分配算法然后让你从源的最短路径，在遍历图中的每个节点。

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基本上只是扩展了一个一步到位的每一个迭代，这恰好有裁断的搜索（链接，边缘，无论你怎么称呼它在你的应用程序）的最小的的步数的需要得到任何给定的节点从源（根）。

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").

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