Graphs & Networks
Dijkstra
When you see it
Signal words
If the prompt uses any of these, this pattern should come to mind first.
shortest pathweightedminimum costcheapestnon-negative weightsfastest
Practice
Drill this pattern with an AI trainer — reply only with Hint, Next, Lost, or paste your code.
Ask yourself
- Shortest path with WEIGHTED, non-negative edges?
- Minimum cost / time to reach a target?
- Min-heap of
(dist, node), relax neighbours.
Classic problem
Network Delay Time (LeetCode 743) — Given a weighted directed graph as times = [u, v, w] edges, find how long it takes for all nodes to receive a signal sent from node k.
Input: times = [["A","B",4],["A","C",2],["C","B",1],["B","D",5],["C","D",8],["D","E",3]], start = "A"
Output: 11 — the longest shortest path is A → C → B → D → E with total weight 2+1+5+3 = 11.
Common pitfalls
Using on negative weights (use Bellman-Ford).
Not skipping stale heap entries.