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 $A$ and $C$. The shortest (in terms of length) is $(A, C)$. However, the shortest (cheapest) in terms of total weight (cost) is $(A, B, D, C)$.

The shortest path problem is generally defined in terms of "cost." We can set the edge weights to $1$, 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 $B$ and $C$ at the same time (both are one edge away from $A$) and concludes the shortest path from $A$ to $C$ is the direct edge $(A,C)$. BST will not update this "shortest" path when it finds the second path (which is cheaper) from $D$ to $C$ because, at that point, $C$ is already "explored."