# Why can't we use BFS with modifications to find shortest paths in weighted graphs

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?

• Which slight modifications did you have in mind?
– trincot
Oct 18 at 15:45

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.