Menu
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:
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!
745
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.
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.
And so, the only possible way for BFS (or DFS) to find the shortest path in a weighted graph is to search the entire graph and keep recording the minimum distance from source to the destination vertex.
Dijkstra's algorithm is more general than BFS,in deed it is a generalization of BFS where edges' weights no longer have to be equal - this is “THE” only significant difference. For efficiency reason,a FIFO queue in BFS generalizes to a priority queue in Dijkstra.
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.
76
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.
32
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
