Shortest Paths

At a glance

The instinct

Plain BFS finds the fewest edges. The moment edges carry different costs (time, price, effort, risk), fewest edges no longer means cheapest, and you need a shortest-path algorithm. The default is Dijkstra: keep a min-heap of (costSoFar, node), pop the cheapest, and use it to improve its neighbours. Because every weight is non-negative, the first time a node leaves the heap its cost is final.

Two follow-up questions pick the exact tool: Can weights be negative? and Is there a limit on the number of edges/stops? Either one moves you to Bellman-Ford.

Recognise it

Not this pattern if...

• All edges cost the same: plain BFS is simpler and O(V + E).
• You need to connect all nodes cheaply (total edge weight), not travel between two: that is a minimum spanning tree.
• The graph is a DAG: relax edges in topological order in O(V + E), no heap needed.
• You need the longest simple path in a general graph: that is NP-hard, not a shortest-path variant.

Memory hack

Analogy: drop a stone in a pond where some channels are shallow (fast) and some are muddy (slow). The ripple reaches each shore at its true earliest time, and once it arrives there it cannot arrive "earlier" later. The heap is just a list of ripple fronts sorted by arrival time.

Say it out loud in the interview:

1. "Edges are weighted and non-negative, so Dijkstra; negative or hop-limited, so Bellman-Ford."
2. "What is the cost of a path - a sum, a product, or a max along the way? It just has to never get better as the path grows."
3. "I will use lazy deletion: if a popped distance is larger than the best known, skip it."

How it works

Every node starts at infinity except the source at 0. Each pop gives the cheapest node still waiting; for each outgoing edge you check whether going through this node beats the neighbour's best known cost (that check-and-update is called relaxation). Improved neighbours are pushed again, so old, larger entries linger in the heap and are discarded when popped.

Trace on edges A→B 4, A→C 1, C→B 2, B→D 1, C→D 5, source A:

Notice step 2: the direct edge A→B looked best at first, but the detour through C was cheaper. That is exactly why BFS fails here.

Bellman-Ford instead relaxes every edge, round after round. After round k, each distance is the best path using at most k edges - which is precisely the "at most K stops" constraint in Cheapest Flights Within K Stops. Copy the distance array each round so one round cannot chain several edges.

Java template

import java.util.*;

class ShortestPath {
    // Dijkstra with lazy deletion. adj.get(u) holds int[]{v, w}; weights must be >= 0.
    static long[] dijkstra(List<List<int[]>> adj, int src) {
        long[] dist = new long[adj.size()];
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[src] = 0;
        PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
        pq.offer(new long[]{0, src});
        while (!pq.isEmpty()) {
            long[] top = pq.poll();
            int u = (int) top[1];
            if (top[0] > dist[u]) continue;            // stale entry
            // optional: if (u == target) return early
            for (int[] e : adj.get(u)) {
                long nd = dist[u] + e[1];              // combine: sum / max / product
                if (nd < dist[e[0]]) {
                    dist[e[0]] = nd;
                    pq.offer(new long[]{nd, e[0]});
                }
            }
        }
        return dist;                                   // Long.MAX_VALUE = unreachable
    }

    // Bellman-Ford limited to at most maxEdges edges. edges[i] = {from, to, w}.
    static int[] bellmanFord(int n, int[][] edges, int src, int maxEdges) {
        final int INF = Integer.MAX_VALUE;
        int[] dist = new int[n];
        Arrays.fill(dist, INF);
        dist[src] = 0;
        for (int round = 0; round < maxEdges; round++) {
            int[] next = dist.clone();                 // read old, write new
            for (int[] e : edges) {
                if (dist[e[0]] != INF && dist[e[0]] + e[2] < next[e[1]]) {
                    next[e[1]] = dist[e[0]] + e[2];
                }
            }
            dist = next;
        }
        return dist;
    }
}

Complexity

On a grid, V = rows × cols and E ≈ 4V.

Variations

• Sum of weights (classic): Network Delay Time - run Dijkstra once and return the maximum distance, or -1 if any node is unreachable.
• Hop-limited: Cheapest Flights Within K Stops - Bellman-Ford for K + 1 rounds, or Dijkstra whose state is (node, stopsUsed).
• Bottleneck / minimax: Path With Minimum Effort and Swim in Rising Water - path cost is max(edge) along the path. Dijkstra works as is; binary search on the answer plus BFS, or union-find over sorted edges, also work.
• Multiplicative: Path with Maximum Probability - use a max-heap and multiply; probabilities in (0, 1] only shrink, which keeps the greedy argument valid.
• 0-1 BFS: Minimum Cost to Make at Least One Valid Path in a Grid - push 0-cost moves to the front of a deque and 1-cost moves to the back.
• State-expanded graph: add extra dimensions to the node (keys collected, fuel left, stops used) and run Dijkstra on (node, extra) pairs.

Common mistakes

• Forgetting the stale check. Without if (d > dist[u]) continue, you re-expand outdated entries; it is usually still correct but can blow up the running time.
• Marking visited on push instead of pop. A node's distance is final only when it is popped, not when it is first discovered.
• Updating in place in hop-limited Bellman-Ford. Writing into the same array lets one round use several edges, silently breaking the "at most K stops" rule. Clone first.
• Integer overflow. INF + w wraps negative; guard with an INF check or use long.
• Using plain Dijkstra with a stop limit. Discarding a path because it is more expensive can throw away the one that had stops left; track stops in the state or use Bellman-Ford.

All practice problems

5 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.