State-Space Shortest Paths (Layered Graphs)

Intuition

Plain shortest-path algorithms assume that the future depends only on the vertex you stand on. Many interview problems break that assumption: "you may ride up to k roads for free", "you may knock down up to k walls", "you must collect every key". Two visits to the same vertex are then not interchangeable: arriving with two free passes left is worth more than arriving with none.

The fix is mechanical: put the missing information into the vertex. Picture k + 1 copies (layers) of the graph. Vertex (v, j) means "standing at v having used j free passes". A normal edge u -> v connects (u, j) to (v, j) with its usual cost. A free pass connects (u, j) to (v, j + 1) with cost 0. Now the plain algorithm runs unchanged on the expanded graph, and the answer is the best of (target, j) over all j.

The same trick is called node splitting in network flow: a vertex with a capacity becomes v_in -> v_out with that capacity on the connecting edge. That use is covered with max flow; here we focus on shortest paths.

When to use it in interviews / OAs

Look for a resource or a memory that changes what you are allowed to do next:

• "at most k discounts / free edges / stops / wall removals" -> state (node, k_used);
• "collect all keys", "visit every node", "pick up all items" with small counts -> state (node, bitmask);
• "path of even length", "alternating colors", "the direction you face" -> state (node, parity or color or direction);
• fuel, battery, time modulo T -> state (node, level).

Then pick the engine by edge costs: all steps cost 1 -> BFS; costs 0/1 -> 0-1 BFS; general non-negative -> Dijkstra.

Template

Dijkstra with up to k free edges

import heapq
from collections import deque

INF = float("inf")


def cheapest_with_free_edges(n: int, edges: list[tuple[int, int, int]],
                             src: int, dst: int, k: int) -> float:
    adj: list[list[tuple[int, int]]] = [[] for _ in range(n)]
    for u, v, w in edges:  # undirected roads
        adj[u].append((v, w))
        adj[v].append((u, w))
    dist = [[INF] * (k + 1) for _ in range(n)]  # dist[v][j]: at v after j free rides
    dist[src][0] = 0
    pq = [(0, src, 0)]
    while pq:
        d, u, j = heapq.heappop(pq)
        if d > dist[u][j]:
            continue
        for v, w in adj[u]:
            if d + w < dist[v][j]:  # pay for the road: stay in layer j
                dist[v][j] = d + w
                heapq.heappush(pq, (d + w, v, j))
            if j < k and d < dist[v][j + 1]:  # ride for free: go up one layer
                dist[v][j + 1] = d
                heapq.heappush(pq, (d, v, j + 1))
    return min(dist[dst])

For "a discount halves the toll", replace the free move's cost 0 with w // 2; nothing else changes.

BFS on (cell, removals left)

Shortest path in a grid when you may walk through at most k obstacles (start and goal are free cells):

def shortest_path_eliminate(grid: list[list[int]], k: int) -> int:
    rows, cols = len(grid), len(grid[0])
    if k >= rows + cols - 2:  # enough removals to walk straight along the border
        return rows + cols - 2
    seen = [[[False] * (k + 1) for _ in range(cols)] for _ in range(rows)]
    seen[0][0][k] = True
    q = deque([(0, 0, k)])
    steps = 0
    while q:
        for _ in range(len(q)):
            r, c, left = q.popleft()
            if r == rows - 1 and c == cols - 1:
                return steps
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < rows and 0 <= nc < cols:
                    nl = left - grid[nr][nc]  # an obstacle uses one removal
                    if nl >= 0 and not seen[nr][nc][nl]:
                        seen[nr][nc][nl] = True
                        q.append((nr, nc, nl))
        steps += 1
    return -1

BFS on (node, visited mask)

Shortest walk that visits every node at least once (n up to about 12), starting anywhere:

def shortest_path_all_nodes(adj: list[list[int]]) -> int:
    n = len(adj)
    full = (1 << n) - 1
    seen = [[False] * (1 << n) for _ in range(n)]
    q = deque()
    for v in range(n):  # every start at once: multi-source BFS
        seen[v][1 << v] = True
        q.append((v, 1 << v))
    steps = 0
    while q:
        for _ in range(len(q)):
            u, mask = q.popleft()
            if mask == full:
                return steps
            for v in adj[u]:
                nm = mask | (1 << v)
                if not seen[v][nm]:
                    seen[v][nm] = True
                    q.append((v, nm))
        steps += 1
    return -1  # the graph is disconnected

Complexity

The expanded graph has n * S vertices and about m * S edges, where S is the number of extra states. So Dijkstra costs O(S * (n + m) log(S * n)) and BFS O(S * (n + m)). With k free edges S = k + 1; with a bitmask over t items S = 2^t, which is why bitmask states only work for t up to about 10 to 15. Always estimate n * S before coding: it is both your time and your memory.

Common pitfalls

• Visited per vertex instead of per state. Marking cell (r, c) as seen the first time throws away later arrivals with more removals left, which may be the only ones that can finish.
• Reading only one layer at the end. The answer is the best over all layers at the target (min(dist[dst])), not dist[dst][k].
• Pruning with the wrong order. In "cheapest flights within k stops", a city reached more cheaply but with more stops does not dominate one reached with fewer stops. Either keep the full (node, stops) table or prune only when a state is worse in both cost and stops.
• Forgetting the shortcut. In the obstacle grid, once k covers a straight path the answer is the Manhattan distance; it also keeps memory small.
• State explosion. (node, mask) with 20 items is a million states per node; check constraints before choosing this route.
• Using BFS when moves have different costs. If a free move and a paid move coexist, you need 0-1 BFS or Dijkstra, not a plain queue.

Interview variations

• Cheapest flights within K stops. State (city, flights_used), or Bellman-Ford with K + 1 rounds.
• Minimum cost to reach a city with discounts. Layer = discounts used; the discounted edge costs w // 2.
• Shortest path to get all keys. BFS over (cell, keys_mask); locks are passable only when the matching bit is set.
• Shortest path with alternating colors. State (node, color of last edge).
• Even-length or parity paths. Two copies of the graph; every edge flips the parity layer.
• Push-the-box puzzles. State (box position, player position); the player's walking can be a nested BFS.
• Minimum time with waiting rules (traffic lights, opening hours). State includes time modulo the period, or Dijkstra where the edge cost depends on arrival time.