41. Weighted Graphs and Shortest Path Problem

In many real-world scenarios, edges in a graph have associated costs (weights). The Shortest Path Problem is crucial here.

Definition

Given a weighted graph and a source node S, the goal is to find the path from S to every other node V such that the sum of the weights along that path is minimized.

Why BFS Fails Here

Remember, BFS finds the shortest path in terms of the number of edges. In a weighted graph, having fewer edges doesn't mean the path is 'shorter' (cheaper). A path with 3 short edges might be cheaper than a path with 2 very long edges.

We need specialized algorithms that account for weights, such as Dijkstra's algorithm.