Using BFS for Weighted Graphs

Question

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 1

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:

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.

Solution 2

Although this is true, but you could use BFS/DFS in weighted graphs, with a little change in the graph, if your graph's weights are positive integers you can replace an edge with weight n with n edges with weight 1 with n-1 middle nodes. Something like this:

A-(4)-B

will be:

A-(1)-M1-(1)-M2-(1)-M3-(1)-B

And don't consider these middle nodes (like M1,M2,M3 ) in your final BFS/DFS results.

---

This algorithm complexity is O(V * M) and M is the maximum weight of our edges, if we know that in our particular graphs M<log V this algorithm could be considerd, but in general this algorithm may not have a such a good performance.

Solution 3

the teacher mentions that BFS/DFS can't be used directly for finding shortest paths in a weighted graph

For starters, DFS is off the table and doesn't work for shortest paths at all.

Secondly, this answer correctly explains why BFS fails on weighted graphs with cycles and suggests Dijkstra's, replacing the queue with a priority queue and allowing relaxation if a new, shorter path is found to a node.

However, it hasn't been mentioned that on a weighted directed acyclic graph (weighted DAG), Dijkstra's is overkill and a single-source shortest path can be found in O(|V|+|E|) time by relaxing each vertex in topological order. This approach also works for DAGs with negative weight edges.

Here's the high-level algorithm:

distances = {V: infinity for V in vertices}
predecessors = {V: None for V in vertices}

for U in topological_sort(vertices):
    for V in adjacencies(U):
        if distances[V] > distances[U] + edge_weight(U, V): # relax the edge
            distances[V] = distances[U] + edge_weight(U, V)
            predecessors[V] = U

Sources:

• Princeton Algorithms, 4ed: 4.4 Shortest Paths
• Wikipedia - Topological sorting: Application to shortest path finding

Comments

[aspen100]

you cannot use DFS to find the shortest path, even in an unweighted graph; BFS can do that.

[user2125722]

Thank you but I've a doubt. You explained how Dijkstra worked for the above example and it chose the path from A->C because it has the lowest edge weight to C. Suppose, The edge from C->B had a weight of 4 and there was an edge from A->D (weight 3) and D->B (weight 1). Going by what you said, the edge A->C and C->B get traversed first, right ? Then, I guess the edge from A->D and D->B has to be traversed even though B has been seen else we would be missing the shortest path. So, how can we ignore that path ? I guess you mentioned that in point 3. Please correct me if I'm wrong ? :/.. Thanks

[Greg]

@user2125722 A->C will be traversed first, as it is the lowest weight edge, followed by A->B and A->D, then D->B, then C->B. If you don't understand why this is the case, try stepping through the pseudocode for the algorithm for this graph.

[Greg]

@user2125722 note that the definition of seen in Dijkstra's algorithm is slightly different. I updated the code to more clearly reflect what actually happens.

[user2125722]

Thanks, I got it now. So, in Dijkstra we check every path ,but in order of the shortest unseen weight ,right ?

[Greg]

@user2125722 yes, you start a few paths from the starting node, and extend the shortest one each time/split it into multiple paths. Since the shortest path so far is always processed first, regardless of how many edges lie on that path, you always end up finding the shortest path to your destination.

[user2125722]

Thanks, this can be done, but it won't be feasible in cases where the weights are quite large, right ?

[user2125722]

@PartiallyFinite I got it .Thanks :D

[user2125722]

@Lrrr You mentioned in your answer that the time complexity is O(V * M), but won't it be dependent on the number of edges as PartiallyFinite mentioned ?