CODEWITHSUNDEEP
algorithmgraphbreadth-first-searchshortest-pathdijkstra
harrythomas
harrythomas

Reputation: 1467

What is difference between BFS and Dijkstra's algorithms when looking for shortest path?

I was reading about Graph algorithms and I came across these two algorithms:

What is the difference between Dijkstra's algorithm and BFS while looking for the shortest-path between nodes?

I searched a lot about this but didn't get any satisfactory answer!

The rules for BFS for finding shortest-path in a graph are:

  1. We discover all the connected vertices,
  2. Add them in the queue and also
  3. Store the distance (weight/length) from source u to that vertex v.
  4. Update with path from source u to that vertex v with shortest distance and we have it!

This is exactly the same thing we do in Dijkstra's algorithm!

So why are the time complexities of these algorithms so different?

If anyone can explain it with the help of a pseudo code then I will be very grateful!

I know I am missing something! Please help!

Upvotes: 72

Views: 39637

Answers (5)

Mohana Sundaram S
Mohana Sundaram S

Reputation: 180

Since you asked for psuedocode this website has visualizations with psuedocode https://visualgo.net/en/sssp

Upvotes: 0

tanweer alam
tanweer alam

Reputation: 437

When using BFS for finding the shortest path in a graph, we discover all the connected vertices, add them to the queue and also maintain the distance from source to that vertex. Now, if we find a path from source to that vertex with less distance then we update it!

We do not maintain a distance in BFS. It is for discovery of nodes. So we put them in a general queue and pop them. Unlike in Dijikstra, where we put accumulative weight of node (after relaxation) in a priority queue and pop the min distance.

So BFS would work like Dijikstra in equal weight graph. Complexity varies because of the use of simple queue and priority queue.

Upvotes: 6

Vishal Sharma
Vishal Sharma

Reputation: 101

Dijkstra and BFS, both are the same algorithm. As said by others members, Dijkstra using priority_queue whereas BFS using a queue. The difference is because of the way the shortest path is calculated in both algorithms.

In BFS Algorithm, for finding the shortest path we traverse in all directions and update the distance array respectively. Basically, the pseudo-code will be as follow:

distance[src] = 0;
q.push(src);

while(queue not empty) {
    pop the node at front (say u)

    for all its adjacent (say v)
        if dist[u] + weight < dist[v]  
             update distance of v 
             push v into queue
}

The above code will also give the shortest path in a weighted graph. But the time complexity is not equal to normal BFS i.e. O(E+V). Time complexity is more than O(E+V) because many of the edges are repeated twice.

Graph-Diagram

Consider, the above graph. Dry run it for the above pseudo-code you will find that node 2 and node 3 are pushed two times into the queue and further the distance for all future nodes is updated twice.

BFS-Traversal-Working

So, assume if there is lot more nodes after 3 then the distance calculated by the first insertion of 2 will be used for all future nodes then those distance will be again updated using the second push of node 2. Same scenario with 3. So, you can see that nodes are repeated. Hence, all nodes and edges are not traversed only once.

Dijkstra Algorithm does a smart work here...rather than traversing in all the directions it only traverses in the direction with the shortest distance, so that repetition of updation of distance is prevented. So, to trace the shortest distance we have to use priority_queue in place of the normal queue.

Dijkstra-Algo-Working

If you try to dry run the above graph again using the Dijkstra algorithm you will find that nodes are push twice but only that node is considered which has a shorter distance.

So, all nodes are traversed only once but time complexity is more than normal BFS because of the use of priority_queue.

Upvotes: 4

CodingLab
CodingLab

Reputation: 1519

With SPFA algorithm, you can get shortest path with normal queue in weighted edge graph.

It is variant of bellman-ford algorithm, and it can also handle negative weights.

But on the down side, it has worse time complexity over Dijkstra's

Upvotes: -1

Timothy Shields
Timothy Shields

Reputation: 79601

Breadth-first search is just Dijkstra's algorithm with all edge weights equal to 1.

Dijkstra's algorithm is conceptually breadth-first search that respects edge costs.

The process for exploring the graph is structurally the same in both cases.

Upvotes: 138

Related Questions