Shortest Path: Weighted Graph

  • Explain why the modified BFS will not find the shortest path in weighted graphs.

Recall: A weighted graph is a labeled graph where the edge labels are numbers.

Notice in the graph above, there are two paths between AA and CC. The shortest (in terms of length) is (A,C)(A, C). However, the shortest (cheapest) in terms of total weight (cost) is (A,B,D,C)(A, B, D, C).

The shortest path problem is generally defined in terms of "cost." We can set the edge weights to 11, giving us the shortest path in terms of length.

Exercise Can BFS be used to find the shortest path when shortest means "cheapest"?

Solution

BFS will not work, as seen in the example graph. BFS will explore BB and CC at the same time (both are one edge away from AA) and concludes the shortest path from AA to CC is the direct edge (A,C)(A,C). BST will not update this "shortest" path when it finds the second path (which is cheaper) from DD to CC because, at that point, CC is already "explored."