Why use Dijkstra's Algorithm if Breadth First Search (BFS) can do the same thing faster?

algorithm graph dijkstra breadth-first-search
gingercat picture gingercat · Sep 29, 2010 · Viewed 52.3k times · Source

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

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

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

Answer

Arkku picture Arkku · Sep 29, 2010

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.

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

Related questions

Difference between Prim's and Dijkstra's algorithms?

What is the exact difference between Dijkstra's and Prim's algorithms? I know Prim's will give a MST but the tree generated by Dijkstra will also be a MST. Then what is the exact difference?

Read More
Understanding Time complexity calculation for Dijkstra Algorithm

As per my understanding, I have calculated time complexity of Dijkstra Algorithm as big-O notation using adjacency list given below. It didn't come out as it was supposed to and that led me to understand it step by step. Each …

Read More
How does Dijkstra's Algorithm and A-Star compare?

I was looking at what the guys in the Mario AI Competition have been doing and some of them have built some pretty neat Mario bots utilizing the A* (A-Star) Pathing Algorithm. (Video of Mario A* Bot In Action) My …

Read More