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

Question

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

• Dijkstra's algorithm
• Breadth-first search

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!

Solution 1

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.

Solution 2

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.

Solution 3

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.

Comments

[harrythomas]

Then why is the difference between time complexities? I mean why do they say that use BFS rather than Dijkstra's when looking for shortest path in non weighted graph?

[Timothy Shields]

@harrythomas Dijkstra's uses a priority queue data structure to keep track of the frontier of unvisited nodes. Breadth-first search uses a regular queue data structure. Operations on a priority queue are O(log n). Operations on a regular queue are O(1). The use of a regular queue in BFS is made possible by all edge weights being 1 - which makes the regular queue effectively behave as a priority queue.