I came across this post about how we can get to all shortest paths from source (u) to destination (v) . If the algorithm is working in O(E + V), why can't we use it (after slight modifications) for weighted graphs? Why do we use a priority Queue in Djikstra's Shortest path Algorithm?
1 Answer
$\begingroup$
$\endgroup$
In non-weighted graphs it is not possible that in the following graph the shortest path from A to C goes via B.
A ----- B
\ /
\ /
\ /
C
That is why in non-weighted graphs it is enough to extend the current search paths with just one edge: In the first cycle we look at A-B and A-C and determine that we have hit C, and so A-C is the shortest path.
With weighted graphs, this way of working could lead to wrong results. Here are some weights:
A --1-- B
\ /
3 1
\ /
C
Here the paths A-B and A-C are also candidates (like in the unweighted graph), but once A-B is visited, the priority queue will receive B-C (as extension of A-B), and that path will get precedence over A-C! This is a scenario that can never happen in an unweighted graph, and so the priority queue is only useful when dealing with weighted graphs.
