1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Which slight modifications did you have in mind? $\endgroup$
    – trincot
    Oct 18 at 15:45
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy