Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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?

like image 422
gingercat Avatar asked Sep 29 '10 00:09

gingercat


People also ask

Why is Dijkstra better than BFS?

BFS calculates the shortest paths in unweighted graphs. On the other hand, Dijkstra's algorithm calculates the same thing in weighted graphs.

Is Dijkstra's algorithm faster than BFS?

If you consider travel websites, these use Dijkstra's algorithm because of weights (distances) on nodes. If you will consider the same distance between all nodes, then BFS is the better choice. For example, consider A -> (B, C) -> (F) with edge weights given by A->B = 10, A->C = 20, B->F = C->F = 5.

Why Dijkstra's algorithm is better?

The main advantage of Dijkstra's algorithm is its considerably low complexity, which is almost linear. However, when working with negative weights, Dijkstra's algorithm can't be used. , if we need to calculate the shortest path between any pair of nodes, using Dijkstra's algorithm is not a good option. .

What is the difference between Dijkstra and breadth first search?

The difference between Dijkstra and BFS is that with BFS we have a simple FIFO queue, and the next node to visit is the first node that was added in the queue. But, using Dijkstra, we need to pull the node with the lowest cost so far. We want to go from A to E using BFS, so, we'll use a simple FIFO queue.


2 Answers

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

like image 50
Arkku Avatar answered Sep 28 '22 11:09

Arkku


If you consider travel websites, these use Dijkstra's algorithm because of weights (distances) on nodes.

If you will consider the same distance between all nodes, then BFS is the better choice.

For example, consider A -> (B, C) -> (F) with edge weights given by A->B = 10, A->C = 20, B->F = C->F = 5.

Here, if we apply BFS, the answer will be ABF or ACF, as both are shortest paths (with respect to the number of edges), but if we apply Dijstra's, the answer will be ABF only because it considers the weights on the connected path.

like image 32
Saurabh Saluja Avatar answered Sep 28 '22 10:09

Saurabh Saluja