Shortest Path Pattern in Java - Interview Preparation Guide

Shortest path is the graph pattern for moving from plain traversal into cost-aware route selection. The main interview skill is not memorizing named algorithms. It is identifying which edge model you have and proving why that model makes BFS, Dijkstra, or Bellman-Ford the right tool.

Pattern Summary Table

Problem Statement

Given a graph and a notion of path cost, compute the minimum distance from a source to a destination or to all nodes.

Typical interview signals:

• the prompt says shortest path, minimum cost, minimum effort, or minimum time
• the graph is weighted or unweighted
• traversal order matters because earlier discovery may or may not be final
• you may need both distance computation and path reconstruction

Pattern Recognition Signals

• Keywords in the problem: shortest path, minimum cost, least effort, network delay, weighted graph, non-negative weights.
• Structural signals: multiple routes may reach the same node, so traversal needs a best-known-distance rule.
• Decision rule: use BFS for unweighted graphs, Dijkstra for non-negative weights, and Bellman-Ford when negative edges are allowed.

Visual Intuition

Choose shortest-path algorithm based on edge weights:

• unweighted: BFS
• non-negative weighted: Dijkstra
• negative edges: Bellman-Ford (advanced)

Pattern 1: BFS Shortest Path (Unweighted)

Problem description: Find the shortest number of edges from src to dst in an unweighted graph.

What we are doing actually:

1. BFS explores nodes in increasing distance order.
2. Store the first distance assigned to each node.
3. The first time we reach dst, that distance is optimal.

public int shortestPathUnweighted(List<List<Integer>> g, int src, int dst) {
    int n = g.size();
    int[] dist = new int[n];
    Arrays.fill(dist, -1);

    Queue<Integer> q = new ArrayDeque<>();
    q.offer(src);
    dist[src] = 0;

    while (!q.isEmpty()) {
        int u = q.poll();
        if (u == dst) return dist[u]; // BFS guarantees first arrival is shortest.

        for (int v : g.get(u)) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1; // One more edge than current node.
                q.offer(v);
            }
        }
    }
    return -1;
}

Debug steps:

• print queue contents and dist array after each expansion
• verify every node gets a distance only once
• test unreachable destination to confirm -1

Pattern 2: Dijkstra (Weighted, Non-negative)

Problem description: Find shortest distances from a source in a graph with non-negative edge weights.

What we are doing actually:

1. Keep the best known distance for every node.
2. Pop the currently cheapest node from the heap.
3. Relax outgoing edges and update neighbors if we found a shorter path.
4. Skip stale heap entries that no longer match dist[u].

public int[] dijkstra(List<List<int[]>> g, int src) {
    int n = g.size();
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;

    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
    pq.offer(new int[]{src, 0});

    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int u = cur[0], d = cur[1];
        if (d != dist[u]) continue; // Ignore stale entry with outdated distance.

        for (int[] edge : g.get(u)) {
            int v = edge[0], w = edge[1];
            if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w; // Better path found through u.
                pq.offer(new int[]{v, dist[v]});
            }
        }
    }
    return dist;
}

Debug steps:

• print (node, distance) when polling from the heap
• trace every successful relaxation u -> v
• verify stale entries are skipped instead of processed

Dry Run (Dijkstra)

Graph edges:

• 0 -> 1 (4)
• 0 -> 2 (1)
• 2 -> 1 (2)

Start src=0:

1. dist=[0,INF,INF], pq=(0,0)
2. pop 0: relax 1=4, 2=1
3. pop 2: relax 1=min(4,1+2)=3
4. pop stale (1,4) skipped, pop (1,3) processed

Final shortest distance to 1 is 3.

This illustrates why stale-entry skipping is required.

Problem 1: Network Delay Time

Dijkstra with source k; answer is max distance if all nodes reachable.

Problem 2: Path With Minimum Effort

Model as weighted graph where edge cost is height difference. Use Dijkstra with relaxation on max-edge-so-far metric.

Common Mistakes

1. Using Dijkstra with negative weights
2. Missing stale-entry skip (if (d != dist[u]) continue)
3. Overflow on distance addition
4. Wrong graph indexing (1-based vs 0-based)

Pattern Variations

• multi-source BFS for distance-to-nearest-source problems
• Dijkstra on grids with directional or effort-based edge costs
• 0-1 BFS when edge weights are only 0 or 1

Pattern Composition (Advanced)

• shortest path + parent reconstruction for actual route output
• shortest path + state expansion when node plus extra condition defines the true state
• Dijkstra + heap discipline for grid and graph optimization problems

Path Reconstruction Tip

If problem asks actual route, maintain parent[] during relax:

if (newDist < dist[v]) {
    dist[v] = newDist;
    parent[v] = u;
}

Then reconstruct by walking from destination to source through parent.

Practice Problems

1. Shortest Path in Binary Matrix (LC 1091)
   LeetCode
2. Network Delay Time (LC 743)
   LeetCode
3. Path With Minimum Effort (LC 1631)
   LeetCode
4. Cheapest Flights Within K Stops (LC 787)
   LeetCode
5. Swim in Rising Water (LC 778)
   LeetCode

Key Takeaways

• shortest-path problems are really graph-cost-model problems
• BFS is correct only when all edges cost the same
• Dijkstra requires non-negative weights and a stale-entry skip or visited discipline
• path reconstruction is a small add-on once the distance logic is correct