World's most popular travel blog for travel bloggers.

Is Dijkstra's algorithm just BFS with a priority queue?

, , No Comments
Question Detail: 

According to this page, Dijkstra's algorithm is just BFS with a priority queue. Is it really that simple? I think not.

Asked By : Barry Fruitman
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10047

Answered By : Shaull

You can implement Dijkstra's algorithm as BFS with a priority queue (though it's not the only implementation).

Dijkstra's algorithm relies on the property that the shortest path from $s$ to $t$ is also the shortest path to any of the vertices along the path. This is exactly what BFS does.

Or in another perspective: how would Dijkstra's algorithm behave if all the weights were 1? Exactly like BFS.

0 comments:

Post a Comment

Let us know your responses and feedback