Graph Shortest Paths Interview Pattern: When to Use It & 5 Practice Problems (2026)

When a coding interview asks you to find the "minimum" something on a graph, you are almost certainly dealing with a shortest‑paths problem. The pattern shows up in many guises—fewest hops between cities, cheapest flight itinerary, minimal time to finish a series of tasks, or the lowest cost to transform one string into another. Recognizing the signals early lets you pick the right algorithm and avoid costly rewrites.

How to Spot a Shortest‑Path Problem

If you see any of these, pause and map the problem to a graph model before you start coding.

A Worked Example: Minimum Cost to Reach the Bottom‑Right of a Grid

Problem statement (paraphrased)

Given an m × n matrix of non‑negative integers, each cell represents a cost to step on it. Starting at the top‑left, move only right or down. Return the minimum total cost to reach the bottom‑right.

Model

• Each cell is a node.
• Edges go to the right and down neighbor with weight equal to the neighbor’s cost.
• All weights are non‑negative → Dijkstra works, but because the graph is a DAG we can also use DP. We'll stick with Dijkstra to illustrate the pattern.

Python implementation

import heapq
from typing import List, Tuple

def min_cost_grid(grid: List[List[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    # distance matrix, initialized to infinity
    dist = [[float('inf')] * cols for _ in range(rows)]
    dist[0][0] = grid[0][0]
    # heap stores (cost, r, c)
    heap: List[Tuple[int, int, int]] = [(grid[0][0], 0, 0)]
    # four possible moves, but we restrict to right/down
    dirs = [(0, 1), (1, 0)]
    while heap:
        cost, r, c = heapq.heappop(heap)
        if (r, c) == (rows - 1, cols - 1):
            return cost  # early exit when we reach target
        if cost != dist[r][c]:
            continue  # stale entry
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if nr < rows and nc < cols:
                new_cost = cost + grid[nr][nc]
                if new_cost < dist[nr][nc]:
                    dist[nr][nc] = new_cost
                    heapq.heappush(heap, (new_cost, nr, nc))
    # fallback (should never happen with valid input)
    return dist[-1][-1]

Complexity

• Time: O(V log V + E log V) → O(m n log (m n)) because each cell is a vertex and each edge is processed once.
• Space: O(V) for the distance matrix and the heap.

Why Dijkstra? The graph is sparse (each node has at most two outgoing edges) and all weights are non‑negative, making the heap‑based approach optimal. A DP solution would be O(m n) time, but the Dijkstra pattern is more general and works when moves are not limited to right/down.

Common Pitfalls and How to Avoid Them

1. Choosing the wrong algorithm – Using BFS on weighted graphs yields incorrect results. Always check edge weights first.
2. Forgetting early exit – In single‑target problems, stop the algorithm as soon as you pop the target from the heap; otherwise you waste time exploring the whole graph.
3. Implicit graph mistakes – When the graph is defined by a formula (e.g., "you can jump from i to i+arr[i]"), generate neighbors on the fly instead of building a huge adjacency list.
4. Off‑by‑one in grid coordinates – Verify bounds before accessing grid[nr][nc].
5. Neglecting visited set – With Dijkstra, a visited set isn’t strictly required if you check cost != dist[r][c], but forgetting it can lead to duplicate processing.

Five Representative Practice Problems

1. "Network Delay Time" (LeetCode style)

Prompt: Given directed edges with travel times, compute how long it takes for a signal to reach all nodes from a source. Return -1 if some nodes are unreachable. Hint: Classic single‑source shortest path with non‑negative weights → Dijkstra with a min‑heap. Use an adjacency list for efficiency.

2. "Word Ladder" (Shortest Transformation Sequence)

Prompt: Transform beginWord to endWord by changing one letter at a time, each intermediate word must exist in a given dictionary. Return the number of steps. Hint: Treat each word as a node; edges exist between words that differ by one character. The graph is unweighted, so BFS yields the answer.

3. "Minimum Cost to Connect All Points" (MST variant)

Prompt: Given points in a plane, connect them with edges whose weight is Manhattan distance. Find the minimum total cost to make the graph connected. Hint: Though the problem asks for a minimum‑spanning‑tree, you can solve it with Prim’s algorithm, which is essentially Dijkstra on a complete graph where you stop when all vertices are visited.

4. "Maximum Profit in Job Scheduling" (Weighted Interval Scheduling)

Prompt: Each job has a start time, end time, and profit. Choose a subset of non‑overlapping jobs to maximize total profit. Hint: Sort jobs by end time and run DP where the transition uses binary search to find the previous compatible job. This is a 1‑D shortest‑path view where edges represent “skip” or “take” decisions.

5. "Cheapest Flight Within K Stops" (Constrained Shortest Path)

Prompt: Find the cheapest price from src to dst with at most K stops. Return -1 if no such route exists. Hint: Use a modified Dijkstra that tracks remaining stops, or run Bellman‑Ford for K+1 iterations. The constraint on stops makes the standard algorithm need a small tweak.

How to Practice This

1. Map before you code – For each new problem, spend a minute drawing the graph model (nodes, edges, weights). Write down the algorithm you think fits.
2. Implement a reusable template – Keep a short Dijkstra/BFS snippet (like the grid example) that you can adapt. Focus on clean heap usage and early exit.
3. Run edge‑case tests – After coding, manually test scenarios with zero‑weight edges, isolated nodes, and maximum‑size inputs to verify both correctness and performance.

---

While practicing, you can use Call Assistant to rehearse your explanation aloud. It will listen, keep your answer on track, and suggest follow‑up details grounded in your own experience.

FAQ

• When should I prefer Bellman‑Ford over Dijkstra? Use Bellman‑Ford when edge weights can be negative or when you need to detect negative‑weight cycles. It runs in O(V E) time, which is acceptable for up to a few thousand edges.
• Is BFS ever enough for weighted graphs? Only if all weights are equal (effectively unweighted). Otherwise BFS will not respect the cost differences and can return a sub‑optimal path.
• How do I handle a graph that’s given implicitly, like a chessboard? Generate neighbors on the fly inside your BFS/Dijkstra loop instead of building a full adjacency list. This keeps memory usage low.
• What’s a good way to debug a wrong shortest‑path answer? Print the distance array after each relaxation step or after each pop from the heap. Compare against a brute‑force solution on a tiny instance to locate where the algorithm diverges.