Graphs — Shortest Path

important mid · part of Skills & Topics · Senior SWE Roadmap · related: DFS · Graphs — Union-Find & MST · Heaps & Priority Queues · Greedy Algorithms

Why this matters / recognition signals

“Shortest path” means different algorithms depending on one detail buried in the problem statement: are the edges weighted? This note assumes graph representation and BFS are already familiar — see DFS for adjacency lists/matrices and the unweighted case, which is a special case of everything here (BFS is Dijkstra where every edge costs exactly 1, so the priority queue degenerates into a plain queue).

Recognition signals:

• “unweighted graph,” “fewest steps/edges,” “minimum number of moves” → BFS (see DFS), not this note
• “minimum cost / cheapest / shortest travel time,” all weights non-negative → Dijkstra’s algorithm
• weights can be negative (e.g., currency arbitrage, penalties/refunds) → Bellman-Ford
• “detect if a negative cycle exists / arbitrage opportunity” → Bellman-Ford’s cycle-detection extension
• “cheapest path with at most K stops/edges” → a hop-bounded relaxation (Bellman-Ford-flavored), not vanilla Dijkstra

Dijkstra’s algorithm

Dijkstra is a greedy algorithm: repeatedly pick the unfinalized node with the smallest known distance, finalize it (its distance can never improve after this point), then relax every edge leaving it — meaning, check if going through this node gives a shorter path to each neighbor, and if so, update that neighbor’s distance.

The greedy step is only safe because edge weights are non-negative. Once a node is popped with the smallest distance in the queue, no other path to it can possibly be shorter — any alternative path would have to go through some other, not-yet-finalized node whose distance is already ≥ the popped node’s distance, and adding any further non-negative edge weight on top can only make that alternative path longer still. That guarantee breaks the moment a negative edge exists (worked example further down).

Worked example — Dijkstra from A

flowchart LR
    A -->|4| B
    A -->|1| C
    C -->|2| B
    C -->|5| D
    B -->|1| D
    D -->|3| E

Implementation uses a min-heap of (distance, node) pairs. Standard library heaps (Java’s PriorityQueue, Python’s heapq) don’t support decrease-key, so instead of updating an entry in place, push a new (shorter distance, node) pair and treat old, now-stale entries as garbage to be skipped when popped (lazy deletion — see the pitfalls section).

Step	Pop (dist, node)	Relax	dist[] after	PQ after (stale entries marked)
1	(0, A)	B: 0+4=4 < ∞ → 4; C: 0+1=1 < ∞ → 1	A0 B4 C1 D∞ E∞	[(1,C), (4,B)]
2	(1, C)	B: 1+2=3 < 4 → 3; D: 1+5=6 < ∞ → 6	A0 B3 C1 D6 E∞	[(3,B), (4,B)stale, (6,D)]
3	(3, B)	D: 3+1=4 < 6 → 4	A0 B3 C1 D4 E∞	[(4,B)stale, (4,D), (6,D)stale]
4	(4, B)	stale — popped dist 4 > dist[B]=3, skip	unchanged	[(4,D), (6,D)stale]
5	(4, D)	E: 4+3=7 < ∞ → 7	A0 B3 C1 D4 E7	[(6,D)stale, (7,E)]
6	(6, D)	stale — popped dist 6 > dist[D]=4, skip	unchanged	[(7,E)]
7	(7, E)	no outgoing edges	A0 B3 C1 D4 E7	[]

Final shortest distances from A: B=3 (via A→C→B, not the direct A→B=4 edge), C=1, D=4 (via A→C→B→D), E=7.

Why negative weights break it

Take A→B = 1, A→C = 4, C→B = -5. Dijkstra pops in order of smallest distance: A(0) first, relaxing B to 1 and C to 4. Next smallest is (1, B), so B gets finalized at distance 1 and its (nonexistent, in this tiny example) outgoing edges get processed. Only after that does (4, C) get popped, relaxing B again: 4 + (-5) = -1, which is smaller than the already-finalized 1 — but Dijkstra has already committed to B=1 and moved on. The true shortest distance to B is -1 (via A→C→B), but Dijkstra reports 1. It doesn’t crash or error — it silently returns a wrong answer, because the “once popped, distance is final” invariant the whole algorithm depends on requires every remaining edge weight to be ≥ 0.

Bellman-Ford — the fix for negative weights

Bellman-Ford drops the greedy priority-queue approach entirely and instead relaxes every edge in the graph, V - 1 times in a row. Why V - 1: the longest possible simple shortest path (no repeated nodes) visits at most V nodes, so it has at most V - 1 edges — V - 1 full relaxation passes are guaranteed to be enough for the true shortest distance to propagate all the way along any such path, however many hops it takes.

Negative-cycle detection: after the V - 1 passes, run one more relaxation pass over every edge. If any edge can still be relaxed (i.e., still produces a shorter distance), that improvement cannot be explained by any simple path — it can only come from a cycle that keeps reducing the total cost every time you loop around it. Concretely: X → Y (1), Y → Z (-1), Z → X (-1) sums to -1 around the cycle, so looping it repeatedly drives the “shortest path” toward -∞ — there is no well-defined finite answer, and that extra pass finding still-improvable edges is exactly how you detect it.

Algorithm	Handles negative weights?	Detects negative cycles?	Time
BFS (unweighted only)	N/A — no weights	N/A	O(V + E)
Dijkstra	No — silently wrong	No	O((V+E) log V) with a binary heap
Bellman-Ford	Yes	Yes (the extra Vth pass)	O(V · E)

Java — Dijkstra (Network Delay Time)

Given directed, weighted edges times[i] = [u, v, w], n nodes, and a starting node k, return the time for a signal to reach every node (the max over all shortest distances), or -1 if some node is unreachable.

public int networkDelayTime(int[][] times, int n, int k) {
    Map<Integer, List<int[]>> graph = new HashMap<>();
    for (int[] t : times) {
        graph.computeIfAbsent(t[0], x -> new ArrayList<>()).add(new int[] { t[1], t[2] });
    }
 
    int[] dist = new int[n + 1];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[k] = 0;
 
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]); // (distance, node)
    pq.offer(new int[] { 0, k });
 
    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int d = curr[0], node = curr[1];
        if (d > dist[node]) continue; // stale entry — a shorter path was already found, skip
 
        for (int[] edge : graph.getOrDefault(node, Collections.emptyList())) {
            int next = edge[0], weight = edge[1];
            int newDist = d + weight;
            if (newDist < dist[next]) {
                dist[next] = newDist;
                pq.offer(new int[] { newDist, next });
            }
        }
    }
 
    int maxDist = 0;
    for (int node = 1; node <= n; node++) {
        if (dist[node] == Integer.MAX_VALUE) return -1; // unreachable node
        maxDist = Math.max(maxDist, dist[node]);
    }
    return maxDist;
}

Python — Dijkstra (Network Delay Time)

import heapq
from collections import defaultdict
 
def network_delay_time(times: list[list[int]], n: int, k: int) -> int:
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))
 
    dist = {node: float("inf") for node in range(1, n + 1)}
    dist[k] = 0
    pq = [(0, k)]  # (distance, node)
 
    while pq:
        d, node = heapq.heappop(pq)
        if d > dist[node]:
            continue  # stale entry — a shorter path was already found, skip
 
        for neighbor, weight in graph[node]:
            new_dist = d + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))
 
    max_dist = max(dist.values())
    return max_dist if max_dist < float("inf") else -1

Complexity comparison

Algorithm	Time	Space	Negative weights?	Notes
BFS (unweighted)	O(V + E)	O(V)	N/A	see DFS
Dijkstra (binary heap)	O((V+E) log V)	O(V + E)	No	greedy, each node finalized exactly once
Dijkstra (array, no heap)	O(V²)	O(V)	No	no log factor, but scans all nodes each round — better for dense graphs
Bellman-Ford	O(V · E)	O(V)	Yes, and detects negative cycles	V-1 relax passes + 1 detection pass

Common pitfalls

• Running Dijkstra on a graph with any negative edge: it doesn’t throw — it returns a plausible-looking but wrong distance, because a node can get finalized before a cheaper path through a not-yet-explored negative edge is discovered.
• Forgetting the stale-entry check: without if d > dist[node]: continue (or the Java equivalent), a plain library heap without decrease-key support will re-process already-finalized nodes with outdated distances, either corrupting results or wasting significant work. Lazy deletion (push duplicates, skip stale pops) is the idiomatic fix — don’t reach for a hand-rolled indexed heap unless profiling actually demands it.
• Misremembering why it’s V - 1 rounds in Bellman-Ford: it’s tied to the maximum number of edges in any simple shortest path (at most V - 1), not an arbitrary constant. Fewer rounds risks an under-relaxed (too-large) distance; the extra Vth round is specifically for cycle detection, not part of the “correct answer” guarantee.
• Treating “cheapest path within K stops” as vanilla Dijkstra: the stop-count constraint means a path with fewer hops can legitimately beat a cheaper-but-more-hops path depending on the remaining budget, so the state must include hops-used, not just node. The standard fix is Bellman-Ford-style relaxation bounded to K rounds, not a greedy Dijkstra pop order (which has no concept of “hops remaining”).
• Reaching for Dijkstra from every source when you need all-pairs shortest paths: that’s O(V · (V+E) log V); if the graph is small and dense, Floyd-Warshall’s simpler O(V³) triple loop is often easier to get right and fast enough.

Practice problems

• Network Delay Time (vanilla Dijkstra)
• Cheapest Flights Within K Stops (hop-bounded Bellman-Ford-style relaxation, not vanilla Dijkstra)
• Path With Minimum Effort (Dijkstra with a non-additive “distance” — the max edge weight along the path, not the sum)
• Swim in Rising Water (Dijkstra variant, or binary search + BFS over a threshold)
• Word Ladder (unweighted — BFS; see DFS)

Interview angles

• “Why does Dijkstra fail with negative weights?” — its greedy finalize-on-pop step assumes a popped node’s distance can never improve later, which only holds if every remaining edge adds a non-negative amount; a negative edge discovered afterward can undercut an already-finalized node.
• “How does Bellman-Ford detect negative cycles, concretely?” — run V-1 relaxation rounds (enough to propagate any negative-cycle-free shortest path), then run one more; if any edge still relaxes, the improvement can only be explained by a cycle you could loop forever to keep lowering the cost — i.e., a negative cycle reachable from the source.
• “Why V-1 rounds and not V or V/2?” — a shortest simple path visits at most V nodes and therefore has at most V-1 edges; V-1 full passes are exactly enough to guarantee that distance has propagated that far.
• “Your priority queue doesn’t support decrease-key — does Dijkstra break?” — no; push duplicate (distance, node) entries and skip any popped entry whose distance exceeds the current best known distance for that node (lazy deletion). Bounded extra memory (at most O(E) entries), no correctness loss.
• “When would you pick Bellman-Ford over Dijkstra even with all-non-negative weights?” — rarely, and mostly not for performance: only when you also need negative-cycle detection as a feature, or the graph is small enough that O(VE) is fine and you want to avoid a heap.
• “How do you adapt shortest-path search for ‘cheapest path with at most K stops’?” — extend the state to (node, stops_used) so a higher-cost path isn’t discarded just because a cheaper one exists with more hops than the budget allows; the standard solve is Bellman-Ford-style relaxation capped at K rounds, since Dijkstra’s pure cost-based greediness has no way to respect a hop-count ceiling.

My Notes