Shortest Path

01 / The shared mechanism

Find the shortest route from a source to every other node. The mechanism splits by what the edges carry — uniform costs collapse to BFS, non-negative weights need a priority queue (Dijkstra), negatives demand relaxation rounds (Bellman-Ford), and full transit tables fall to Floyd-Warshall.

01 / The one-sentence essence

When edge weights are non-negative, the unvisited node with the smallest tentative distance can never be improved by routing through any other unvisited node — so a min-priority-queue, popping the closest node each round and relaxing its outgoing edges, finalizes shortest distances in one pass.

Problemshortest path from source on a non-negative weighted graphGraphmeshSourceA

Graph has 6 nodes. Mark every distance as ∞ and push the source onto the priority queue.

step

0 / 47

—

finalized

0 / 6

0 / 47

sourcegraph

02 / The pattern signature

# Dijkstra from source — non-negative edge weightsdist[v] ← ∞ for all vdist[s] ← 0pq ← min-heap of (0, s)while pq not empty:(d, u) ← pq.pop_min() # pop minif d > dist[u]: continuefor (v, w) in neighbors(u): # relaxif dist[u] + w < dist[v]:dist[v] ← dist[u] + wpq.push((dist[v], v)) # decrease-key or push duplicate

03 / When to recognize this pattern

"non-negative weights"

Edges carry positive (or zero) costs — distance, time, money, latency. If any weight can be negative, Dijkstra silently gives wrong answers; use Bellman-Ford.

"minimum cost / shortest distance"

The objective sums edge weights, not hop counts. "Cheapest", "minimum total time", "least effort path" — anything that accumulates a non-negative cost along the route.

"single source, many targets"

One source, distances to every other node — or to a specific destination. One Dijkstra run gives both; for the single-destination case, you can early-exit when the target pops.

"priority queue / min-heap"

The data structure is the algorithm. Always pull the smallest tentative distance next — a plain queue or stack will not work, because non-uniform weights mean the first time you touch a node may not be the shortest way to reach it.

04 / Common pitfalls

Running Dijkstra on a graph with negative edges.

Once a node is popped and finalized, Dijkstra never revisits it — but a later negative edge could still improve its distance. The algorithm fails silently: no error, just a wrong answer. Use Bellman-Ford when any edge can be negative.

ii.

Forgetting the stale-entry check.

Most implementations push a new (dist, v) on every relax instead of doing a true decrease-key, so the heap accumulates outdated entries. When you pop, you must skip if d > dist[u]; otherwise you re-process the node and inflate the running time.

iii.

Using plain Dijkstra under an extra constraint like "at most K stops".

Dijkstra optimizes only the cumulative cost. Add a hop or stop cap (LC 787) and the shortest path may need more stops than the cheapest one, so the greedy "pop minimum" assumption breaks. Switch to BFS-with-state, Bellman-Ford with K relax rounds, or modified Dijkstra keyed by (cost, stops).

05 / Go practice — on LeetCode

Four problems, ordered by difficulty. No solutions here, by design.

01Network Delay Time— LC 743medium→02Path With Minimum Effort— LC 1631medium→03Path with Maximum Probability— LC 1514medium→04Cheapest Flights Within K Stops— LC 787medium→

— / When to use which

unweighted BFS

Use when every edge has the same cost — 1 step = 1 edge.

grid · maze · O(V + E)

Dijkstra

Use when edge weights are non-negative.

priority queue · O((V + E) log V)

Bellman-Ford

Use when weights can go negative, or you need cycle detection.

V−1 relax rounds · O(V · E)

Floyd-Warshall

Use when you need all-pairs distances, not just single-source.

DP via intermediates · O(V³)