Pattern Recognition Drill
Medium Advanced Graphs
The Problem
Shortest path from source in a weighted graph.
What approach would you use?
Think about it before scrolling down.
Min-heap of (distance, node). Pop closest, relax edges. First pop of each node is shortest. O((V+E) log V).
BFS only works for unweighted graphs. For weighted, you MUST use Dijkstra or Bellman-Ford.
Common Trap
Using BFS on weighted graphs gives WRONG answers. The heap ensures you process closest first.