patternMajor
Is Dijkstra's algorithm just BFS with a priority queue?
Viewed 0 times
prioritydijkstrajustwithbfsalgorithmqueue
Problem
According to this page, Dijkstra's algorithm is just BFS with a priority queue. Is it really that simple? I think not.
Solution
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.
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.
Context
StackExchange Computer Science Q#10047, answer score: 32
Revisions (0)
No revisions yet.