Layered Graph Techniques, in depth: counter layers, hop-limited sweeps, min-plus powers, time-expanded flows and level graphs

Building a layered graph

Start with a directed graph G with V vertices and E weighted edges, and a counter that ranges over 0 to K. The layered graph has a vertex (v, i) for every vertex v and every counter value i, so (K+1)V vertices. Its edges come in three kinds. In-layer edges copy G inside each layer: (u, i) to (v, i) with the original weight. Cross-layer edges model the special event: (u, i) to (v, i+1) with whatever cost that event has. Wait or stay edges, used in the time-based families, go from (v, i) to (v, i+1) and mean doing nothing while the counter advances.

The answer is then read off a set of target vertices, usually the minimum over all layers of the distance to (t, i), because using fewer than K special events is normally allowed. Forgetting that minimum and reading only (t, K) is the most common bug, and it silently returns infinity whenever the best path does not use every allowance.

The property that matters most is monotonicity. If every cross-layer edge goes from layer i to a higher layer, the layers are ordered and no path ever comes back down. That means you can process the layers one after another, finishing layer i before touching layer i+1, and the structure between layers is acyclic even when G is full of cycles. Every family below exploits that ordering in a different way.

Counter layers: K free edges with Dijkstra

The textbook example: find the cheapest route from s to t when you may traverse up to K edges for free. The counter is the number of free edges used. In-layer edges cost their weight, cross-layer edges cost zero. All weights are non-negative, so Dijkstra works on the layered graph unchanged. You rarely build it explicitly; you store a distance per (vertex, layer) pair and generate neighbours on the fly.

Each popped state (u, k) relaxes two neighbours per edge: (v, k) at cost w and, if k is below K, (v, k+1) at cost zero, and the answer is the minimum of dist[t][k] over all k. The cost is O((K+1)E log((K+1)V)) time and O((K+1)V) memory. The same shape covers a discount that halves an edge, a limited number of teleports, or a bounded number of rule violations. The Dijkstra deep dive traces this search step by step, so this page moves on to the families where the layer ordering itself is the algorithm.

Hop layers: at most K edges

Now change the counter to the number of edges used and ask for the cheapest path with at most K edges; the familiar form is cheapest flights with at most K stops, which is K+1 edges. Here every edge, not just a special one, moves up a layer, so there are no in-layer edges at all. The layered graph is a DAG by construction, and the right algorithm is not Dijkstra but a layer-by-layer sweep: compute all of layer i+1 from layer i, K times. That is exactly Bellman-Ford stopped after K rounds.

def at_most_k_edges(n, edges, s, t, K):
    INF = float("inf")
    prev = [INF] * n
    prev[s] = 0
    for _ in range(K):                    # layer i -> layer i+1
        cur = prev[:]                     # staying put = using fewer edges
        for u, v, w in edges:
            if prev[u] + w < cur[v]:      # read prev, never cur
                cur[v] = prev[u] + w
        prev = cur
    return prev[t]

The copy into a fresh array is the whole point. Standard Bellman-Ford updates one array in place, which is fine when you want the true shortest path, because extra relaxations only help. With a hop limit an in-place update lets one round chain several edges, so after K rounds you may hold a path with more than K edges. Starting the next layer as a copy of the previous one encodes at most rather than exactly; start it at infinity instead if you need exactly K edges. Time is O(KE), memory O(V), and negative edges are allowed because the layered DAG has no cycles to go wrong.

Worked example: cheapest route within K edges

Take four airports 0 to 3 with flights 0 to 1, 1 to 2 and 2 to 3 at 100 each, 0 to 2 at 500, 1 to 3 at 600 and a direct 0 to 3 at 1000. The table shows the value at airport 3 as each layer is computed.

Plain Dijkstra returns 300 regardless of K. The in-place sweep with edges in the order above and K = 1 relaxes 0 to 1, 1 to 2 and 2 to 3 within one round and also returns 300 for a one-edge budget.

Exactly k edges with min-plus powers

Sometimes you need exactly k edges and k is huge, say 10 to the 9th, for a walk of fixed length in a state machine. The layered graph would have a billion layers, but every layer is identical, so the transition from one layer to the next is the same matrix each time. Replace sum-of-products matrix multiplication with min-of-sums, and the k-th power of the weight matrix holds the cheapest exactly-k walk between every pair. Repeated squaring computes that power in O(V cubed times log k).

INF = float("inf")

def min_plus(A, B):
    n = len(A)
    return [[min(A[i][m] + B[m][j] for m in range(n)) for j in range(n)]
            for i in range(n)]

def exactly_k(W, k):
    """W[i][j] = edge weight or INF. Returns cheapest walks of exactly k edges."""
    n = len(W)
    R = [[0 if i == j else INF for j in range(n)] for i in range(n)]   # identity
    P = W
    while k:
        if k & 1:
            R = min_plus(R, P)
        P = min_plus(P, P)
        k >>= 1
    return R

The identity for min-plus has zeros on the diagonal and infinity elsewhere, not ones and zeros, and getting that wrong is the classic bug. If you want at most k instead of exactly k, put a zero self-loop on every vertex before powering. Use this only for small V; for sparse graphs with modest k the sweep is far cheaper.

Time-expanded networks for flows over time

The biggest payoff of layering is in flows over time. An evacuation, a fleet of trucks or packets through links with latency all have capacities per time step and travel times. Static max flow ignores time entirely. The time-expanded network makes one copy of every place per time step t = 0 to T. An arc u to v with travel time tau and capacity c becomes an arc from (u, t) to (v, t + tau) with capacity c for every t, and a holdover arc (v, t) to (v, t+1) lets units wait, with capacity equal to how many can be stored at v. A super-source feeds (s, 0) and every (exit, t) drains to a super-sink. Any max-flow algorithm then answers the question how many units can be out by time T.

def build_time_expanded(n, arcs, store_cap, supply, exit_v, T):
    """arcs: (u, v, capacity_per_step, travel_time). Returns arc list for max flow."""
    nid = lambda v, t: v * (T + 1) + t
    S, SINK = n * (T + 1), n * (T + 1) + 1
    out = []
    for t in range(T + 1):
        for u, v, cap, tau in arcs:
            if t + tau <= T:
                out.append((nid(u, t), nid(v, t + tau), cap))
        if t < T:
            for v in range(n):
                out.append((nid(v, t), nid(v, t + 1), store_cap[v]))   # wait
        out.append((nid(exit_v, t), SINK, float("inf")))
    for v, amount in supply.items():
        out.append((S, nid(v, 0), amount))
    return S, SINK, out          # feed to any max-flow routine

Worked example: ten people at place 0, a fast corridor 0 to 1 to 3 with one step per hop and capacity 2 per step, a slow route 0 to 2 taking two steps with capacity 1 and then 2 to 3 taking one step, and intermediate places that can hold 2 waiting people. Running Edmonds-Karp on the expanded network gives the number out by each horizon: 0 by T = 1, 2 by T = 2, 5 by T = 3, 8 by T = 4 and all 10 by T = 5. Binary search on T over the same construction gives the quickest evacuation time. The network has (T+1)V vertices, so the honest cost is that it grows with the horizon; when T is large, coarsen the time step or use the dedicated quickest-flow algorithms instead.

Level graphs inside Dinic and Hopcroft-Karp

Layering also appears inside algorithms you already know. Dinic computes BFS distances from the source in the residual graph and keeps only edges that go from level d to level d+1. The result, the level graph, is a layered DAG, and blocking flow on it can be found with simple DFS that never loops. Each phase strictly increases the source-to-sink distance, which is where the bound of at most V phases comes from. Hopcroft-Karp does the same for bipartite matching: BFS from all free left vertices builds layers that alternate between unmatched and matched edges, and a DFS finds a maximal set of vertex-disjoint shortest augmenting paths through those layers, giving O(E times the square root of V).

Whenever every edge you care about goes up a level, you get acyclicity, DP in level order and easy termination arguments for free. 0-1 BFS is another case: its deque holds at most two adjacent distance levels at a time.

Choosing a family and sizing it

Use the table to pick the family for a problem.

Build implicitly when you can: a vertex-by-layer distance array with edges generated on demand, because materialising (K+1)E edge objects is what blows memory. Build explicitly only when handing the graph to a library max-flow or min-cost-flow solver.

A large, real-valued or multi-dimensional budget does not belong in layers; that is the territory of resource-constrained shortest path, where labels with dominance replace exhaustive layers.

Failure modes

• Reading only the top layer. The answer is the minimum over all layers for at-most constraints. Reading only (t, K) returns infinity or a worse path.
• In-place relaxation in a hop-limited sweep. One round chains several edges. Always read from the previous layer.
• Off-by-one on stops versus edges. K stops means K+1 edges. Write the conversion once, in a named variable.
• Wrong identity in min-plus. The identity is 0 on the diagonal and infinity elsewhere.
• Missing wait arcs. A time-expanded network without holdover arcs forces units to move every step and understates throughput; holdover capacity equal to infinity overstates it if storage is really limited.
• Non-monotone cross edges. If an edge can lower the counter, for example a refuel that resets a fuel counter, the layers are no longer a DAG. Dijkstra still works with non-negative weights, but layer-by-layer sweeps do not.

Trade-offs

Layering trades memory and time linear in K for simplicity: you reuse a proven algorithm, and its correctness proof carries over because the layered graph is just a graph. The price is that dimensions multiply, so two counters of size 50 give 2,500 copies. For time, expansion is exact but grows with the horizon, while specialised flow-over-time algorithms are compact but harder to adapt.

What to do next

1. Write the constraint as a counter and state its range. If the range is not small and integer, stop and look at label-setting methods instead.
2. Decide what moves between layers: special edges only, every edge, or time. That chooses the family.
3. Check monotonicity. If layers only go up, prefer a level-by-level sweep with two rows of memory.
4. Implement with a vertex-by-layer distance array and implicit edges; build explicitly only for library solvers.
5. Read the answer as the minimum over the valid target layers, and test against brute force on random graphs with five vertices, including K = 0.
6. Estimate states and transitions before running on production data.