Search code examples
algorithmgraphshortest-pathbreadth-first-search

Using BFS for Weighted Graphs

I was revising single source shortest path algorithms and in the video, the teacher mentions that BFS/DFS can't be used directly for finding shortest paths in a weighted graph (I guess everyone knows this already) and said to work out the reason on your own.

I was wondering the exact reason/explanation as to why it can't be used for weighted graphs. Is it due to the weights of the edges or anything else ? Can someone explain me as I feel a little confused.

PS: I went through this question and this question.

Solution

  • Consider a graph like this:

    A---(3)-----B
|           |
\-(1)-C--(1)/

    The shortest path from A to B is via C (with a total weight of 2). A normal BFS will take the path directly from A to B, marking B as seen, and A to C, marking C as seen.

    At the next stage, propagating from C, B is already marked as seen, so the path from C to B will not be considered as a potential shorter path, and the BFS will tell you that the shortest path from A to B has a weight of 3.

    You can use Dijkstra's algorithm instead of BFS to find the shortest path on a weighted graph. Functionally, the algorithm is very similar to BFS, and can be written in a similar way to BFS. The only thing that changes is the order in which you consider the nodes.

    For example, in the above graph, starting at A, a BFS will process A --> B, then A --> C, and stop there because all nodes have been seen.

    On the other hand, Dijkstra's algorithm will operate as follows:

    1. Consider A --> C (since this is the lowest-edge weight from A)
    2. Consider C --> B (since this is the lowest-weight edge from any node we have reached so far, that we have not yet considered)
    3. Consider and ignore A --> B since B has already been seen.

    Note that the difference lies simply in the order in which edges are inspected. A BFS will consider all edges from a single node before moving on to other nodes, while Dijkstra's algorithm will always consider the lowest-weight unseen edge, from the set of edges connected to all nodes that have been seen so far. It sounds confusing, but the pseudocode is very simple:

    create a heap or priority queue
place the starting node in the heap
dist[2...n] = {∞}
dist[1] = 0
while the heap contains items:
   vertex v = top of heap
   pop top of heap
   for each vertex u connected to v:
       if dist[u] > dist[v] + weight of v-->u:
           dist[u] = dist[v] + weight of edge v-->u
           place u on the heap with weight dist[u]

    This GIF from Wikipedia provides a good visualisation of what happens:

    Dijkstra

    Notice that this looks very similar to BFS code, the only real difference is the use of a heap, sorted by distance to the node, instead of a regular queue data structure.