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

Repeatedly relax every edge: after V−1 full passes, every shortest path (which has at most V−1 edges) has been discovered — even when some edges are negative.

Problemsingle-source shortest path, weights may be negativeGraphwith-negativeSourceA

Graph has 5 nodes — we will run 4 relax rounds. Initialize all distances to ∞.

step

0 / 66

round

0 / 4

last relax

no change

neg-cycle

—

0 / 66

sourcegraph

02 / The pattern signature

# Bellman-Ford from source — weights may be negativedist[v] ← ∞ for all vdist[s] ← 0# V−1 rounds — a shortest path uses at most V−1 edgesfor round in 1 .. V−1:for (u, v, w) in edges:# relaxif dist[u] + w < dist[v]:dist[v] ← dist[u] + w# negative cycle check — one more passfor (u, v, w) in edges:if dist[u] + w < dist[v]: return "negative cycle"

03 / When to recognize this pattern

"negative edge weights"

The defining cue. Costs can be negative — refunds, gains, currency arbitrage. Dijkstra is unsafe here; Bellman-Ford is the standard tool.

"detect a negative cycle"

Run the V−1 rounds, then do one more pass. If any edge still relaxes, a negative cycle is reachable from the source.

"at most K edges / K stops"

Cap the number of relax rounds at K instead of V−1. After K rounds, dist[v] is the shortest path using at most K edges — the classic Bellman-Ford application.

"arbitrage / currency exchange"

Take −log(rate) as edge weight. A negative cycle then corresponds to a profit loop — Bellman-Ford finds it.

04 / Common pitfalls

Using Dijkstra on a graph with negative edges.

Once a node is finalized in Dijkstra, a later negative edge can no longer revise its distance — wrong answer with no warning. If any edge weight can be negative, you must use Bellman-Ford (or SPFA / Johnson's).

ii.

Stopping at V−1 rounds without checking for a negative cycle.

Distances finalize after V−1 rounds only if no negative cycle is reachable. Always run one extra pass: if anything still relaxes, the answer is "negative cycle", not a number.

iii.

Overflow on dist[u] + w when dist[u] = ∞.

Skip the relaxation when dist[u] is still infinity — otherwise ∞ + (−w) can wrap around to a finite number and silently corrupt the distances. Guard the addition.

05 / Go practice — on LeetCode

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

01Network Delay Time— LC 743medium→02Cheapest Flights Within K Stops— LC 787medium→03Minimum Cost to Reach Destination in Time— LC 1928hard→04Second Minimum Time to Reach Destination— LC 2045hard→

— / 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³)