The Product Graph Lifting Principle
Suppose we want the shortest path from $s$ to $t$ in $G = (V, E, w)$, given at most $K$ uses of a special transition (e.g., halving or zeroing an edge's weight). In the base graph $G$, reaching $u$ with cost $10$ and $0$ coupons left is incomparable to reaching $u$ with cost $15$ and $2$ coupons left. We restore total ordering per state by defining the $(K+1)$-Layer Graph:
For each original vertex $u \in V$ and layer $k \in \{0, 1, \dots, K\}$, create state $(u, k)$ indexed in a flat 1D array as $\text{id}(u, k) = u \cdot (K + 1) + k$. For each original edge $(u, v)$ of weight $w$:
- Intra-Layer Transition (Normal Edge): For all $0 \le k \le K$, add edge $(u, k) \to (v, k)$ with weight $w$.
- Inter-Layer Transition (Coupon / State Upgrade): For all $0 \le k < K$, add edge $(u, k) \to (v, k + 1)$ with discounted weight $0$ (or $\lfloor w / 2 \rfloor$).
Then $\min_{0 \le k \le K} \text{dist}[(t, k)]$ is the exact optimal answer in $O(K(V + E) \log(KV))$ time!
Common State-Space Modeling Patterns
- Fuel Tank / Battery Capacity ($V \times [0..F]$): At state $(u, f)$, either buy $1$ unit of fuel at price $p[u]$ via transition $(u, f) \to (u, f+1)$ of weight $p[u]$, or drive an edge $(u, v)$ of length $L \le f$ via transition $(u, f) \to (v, f - L)$ of weight $0$.Notice that splitting fuel refilling into $+1$ increments keeps out-degree $O(\text{deg}(u) + 1)$ instead of $O(\text{deg}(u) + F)$!
- Bitmask Keys & Locks ($V \times [0..2^K - 1]$): When a maze has $K \le 12$ keys and locked doors, state $(u, \text{mask})$ transitions to $(v, \text{mask} \mid \text{keysAt}[v])$ whenever $(\text{mask} \,\&\, \text{requiredDoor}[u][v]) == \text{requiredDoor}[u][v]$.
- Edge Parity / Modulo-$M$ Path Length ($V \times [0..M-1]$): Finding the shortest path of even/odd length or weight divisible by $M$ uses state $(u, r)$ where $r \in [0, M-1]$ is the remainder modulo $M$.
Compare Dijkstra’s uniform radial frontier against A* directional pruning f(u) = g(u) + h(u) and OSRM Contraction Hierarchies (shortcut insertion w(u,w)=w(u,v)+w(v,w) + upward rank-monotonic bidirectional search).
Invariant & State
Never allocate a physical adjacency list for $G_K$! Generating $K$ copies of $E$ edges wastes $O(K \cdot E)$ memory and pollutes L3 cache. Instead, keep the original graph $G$ read-only in L1/L2 cache, flatten the distance table to dist[u * (K + 1) + k], and generate the intra-layer and inter-layer transitions on-the-fly inside the Dijkstra loop.
Complexity Matrix
| State Space Model | Expanded Vertices $|V'|$ | Expanded Edges $|E'|$ | Total Time Complexity |
|---|---|---|---|
| $K$-Coupon Layered Graph | V · (K + 1) | 2 · E · K | O(K(V + E) log(KV)) |
| Fuel Tank ($+1$ Unit Refill) | V · (F + 1) | (V + E) · F | O(F(V + E) log(FV)) |
| Bitmask Keys ($K$ Keys) | V · 2^K | E · 2^K | O(2^K (V + E) log(V 2^K)) |
Production Implementation: Implicit Layered Dijkstra ($K$ Free Edges)
#include <vector>
#include <queue>
#include <limits>
#include <algorithm>
struct FlightEdge {
int to;
long long cost;
};
long long shortestPathWithKCoupons(int n, int kMax, int src, int dst,
const std::vector<std::vector<FlightEdge>>& adj) {
constexpr long long INF = std::numeric_limits<long long>::max() / 4;
const int stride = kMax + 1;
std::vector<long long> dist(n * stride, INF);
using State = std::pair<long long, int>; // (cost, encodedState = u * stride + k)
std::priority_queue<State, std::vector<State>, std::greater<State>> pq;
dist[src * stride + 0] = 0;
pq.emplace(0, src * stride + 0);
while (!pq.empty()) {
auto [d, state] = pq.top();
pq.pop();
if (d > dist[state]) continue;
int u = state / stride;
int k = state % stride;
if (u == dst) return d; // First time any layer of dst is popped is global min!
for (const auto& e : adj[u]) {
// 1. Normal edge on layer k
int nextSame = e.to * stride + k;
if (d + e.cost < dist[nextSame]) {
dist[nextSame] = d + e.cost;
pq.emplace(dist[nextSame], nextSame);
}
// 2. Coupon transition to layer k + 1 (if available)
if (k < kMax) {
int nextUp = e.to * stride + (k + 1);
if (d < dist[nextUp]) {
dist[nextUp] = d;
pq.emplace(dist[nextUp], nextUp);
}
}
}
}
return -1;
}In layered graphs where a larger resource $k$ is strictly worse (i.e., $k$ counts coupons used), if you already have $\text{dist}[v][k'] \le d_{\text{new}}$ for some $k' < k$, then state $(v, k)$ is Pareto-dominated by $(v, k')$ and never needs to be pushed! Checking dominance or propagating downward bounds across layers prevents redundant heap expansions.