Pattern Guide
Graph State Space Search
"BFS/Dijkstra on augmented states. (node, extra_state) as graph vertices."
Many graph problems require tracking extra state alongside position: (node, fuel_remaining), (node, health), (node, visited_bitmask), (node, num_stops). Model these as a new graph where each "vertex" is (original_node, extra_state). BFS finds shortest path if uniform cost; Dijkstra handles weighted. State space can be O(V × S) where S = number of extra state values.
Problems you can solve with this pattern
4 problems · click any to start solving
// Cheapest Flights Within K Stops — Dijkstra on (cost, node, stops_remaining)
function cheapestFlights(n, flights, src, dst, k) {
const adj = Array.from({length: n}, () => []);
for (const [u, v, w] of flights) adj[u].push([v, w]);
// dist[node][stops] = min cost to reach node with stops remaining
const dist = Array.from({length: n}, () => new Array(k+2).fill(Infinity));
dist[src][k+1] = 0;
// Min-heap: [cost, node, stops_remaining]
const heap = [[0, src, k+1]];
while (heap.length) {
heap.sort((a,b) => a[0]-b[0]); // simple priority queue
const [cost, u, stops] = heap.shift();
if (u === dst) return cost;
if (stops === 0) continue;
for (const [v, w] of adj[u]) {
const newCost = cost + w;
if (newCost < dist[v][stops-1]) {
dist[v][stops-1] = newCost;
heap.push([newCost, v, stops-1]);
}
}
}
return -1;
}State space graph: vertex = (position, extra_state). Edge exists when you can transition from one state to another. BFS on this graph finds minimum steps; Dijkstra finds minimum cost. Key: choose state representation carefully — too coarse loses information, too fine causes exponential blowup. Common extra states: remaining fuel, remaining moves, number of obstacles eliminated, visited bitmask (for small sets).
// Cheapest Flights Within K Stops — Dijkstra on (cost, node, stops_remaining)
function cheapestFlights(n, flights, src, dst, k) {
const adj = Array.from({length: n}, () => []);
for (const [u, v, w] of flights) adj[u].push([v, w]);
// dist[node][stops] = min cost to reach node with stops remaining
const dist = Array.from({length: n}, () => new Array(k+2).fill(Infinity));
dist[src][k+1] = 0;
// Min-heap: [cost, node, stops_remaining]
const heap = [[0, src, k+1]];
while (heap.length) {
heap.sort((a,b) => a[0]-b[0]); // simple priority queue
const [cost, u, stops] = heap.shift();
if (u === dst) return cost;
if (stops === 0) continue;
for (const [v, w] of adj[u]) {
const newCost = cost + w;
if (newCost < dist[v][stops-1]) {
dist[v][stops-1] = newCost;
heap.push([newCost, v, stops-1]);
}
}
}
return -1;
}- (node, steps_remaining) → BFS/Bellman-Ford per step
- (node, fuel) → Dijkstra, O(V × fuel_max)
- (node, bitmask) → TSP-style, O(V × 2^V)
- (node, obstacles_removed) → BFS, O(rows × cols × k)
Key insight: If extra state is bounded, the state space is tractable. If unbounded, need to prune or use greedy instead.
BFS vs Dijkstra on state space: BFS works when all transitions have equal cost. Dijkstra when costs vary. Both use the same state representation — just different priority mechanisms.