Multistage Graph Using Dynamic Programming
A multistage graph is a directed, weighted graph whose nodes are divided
into stages, and every edge goes from one stage to the next (i.e., forward
direction).
It is commonly used to solve shortest path or least-cost path problems.
Structure of a Multistage Graph
● Nodes are arranged in k stages.
● A node belongs to exactly one stage.
● Edges go only from stage i to stage i+1.
● There is a single source (start) in stage 1 and a destination (finish) in
stage k.
Goal
Find the minimum-cost path from the source node (stage 1) to the
destination node (stage k).
Dynamic programming works perfectly because each subproblem (shortest
path from a node to the destination) depends only on the next stage.
Algorithm Steps
1. Number the nodes from last stage to first stage.
2. Set the cost of destination node = 0.
3. Move backwards, stage by stage.
4. At each node, compute the minimal cost using the DP formula.
5. Store the decision (next node) to reconstruct the final path.
Pseudocode
Input:
● n = number of nodes
● cost[n] = DP array
● next[n] = stores the next node in the optimal path
● G[i] = list of (neighbor, weight) pairs for node i
● dest = destination node
Nodes are assumed to be numbered from 1 to n, and arranged in stages.
MULTISTAGE_GRAPH(G, n, dest):
// Step 1: Initialize
cost[dest] = 0
// Step 2: Process nodes backwards from (n-1) to 1
for i from n-1 down to 1:
cost[i] = +infinity
// for all outgoing edges i → j
for each (j, w) in G[i]:
if w + cost[j] < cost[i]:
cost[i] = w + cost[j]
next[i] = j
return cost[1], next
Time Complexity
Let:
● n = number of nodes
● e = number of edges
The algorithm examines each edge exactly once:
T(n)=O
Because:
● Outer loop runs n times
● Inner loop processes all edges across entire algorithm → e
Final Time Complexity:
⭐ O(e) (linear in number of edges)
Space Complexity
We store:
● cost[n]
● next[n]
● adjacency list G storing all edges → size = O(e)
Thus:
S(n)=O(n+e)
If counting only DP storage (not graph storage):
→ O(n)
Multistage Graph Example (Graph Format)
We will use a 4-stage multistage graph:
Stage 1: (1)
Stage 2: (2) (3)
/ \ / \
Stage 3: (4) (5) (6)
\ | /
Stage 4: (7)
Edges with weights
1 → 2 (2), 1 → 3 (3)
2 → 4 (5), 2 → 5 (4)
3 → 5 (6), 3 → 6 (7)
4 → 7 (4)
5 → 7 (2)
6 → 7 (3)
Goal:
Find minimum-cost path from node 1 to node 7.
✅ Step-by-Step DP Solution
We compute cost[i] = minimum cost from node i to destination (7)
Start from the last stage (destination).
STEP 1 — Initialize Destination
cost[7] = 0
STEP 2 — Stage 3 Calculation (nodes 4, 5, 6)
Node 4:
4 → 7 (4)
cost[4] = 4 + cost[7] = 4 + 0 = 4
next[4] = 7
Node 5:
5 → 7 (2)
cost[5] = 2 + cost[7] = 2
next[5] = 7
Node 6:
6 → 7 (3)
cost[6] = 3 + cost[7] = 3
next[6] = 7
STEP 3 — Stage 2 Calculation (nodes 2, 3)
Node 2:
Outgoing:
● 2 → 4 = 5 + cost[4] = 5 + 4 = 9
● 2 → 5 = 4 + cost[5] = 4 + 2 = 6 ← minimum
cost[2] = 6
next[2] = 5
Node 3:
Outgoing:
● 3 → 5 = 6 + cost[5] = 6 + 2 = 8
● 3 → 6 = 7 + cost[6] = 7 + 3 = 10
cost[3] = 8
next[3] = 5
STEP 4 — Stage 1 Calculation (node 1)
Outgoing:
● 1 → 2 = 2 + cost[2] = 2 + 6 = 8
● 1 → 3 = 3 + cost[3] = 3 + 8 = 11
cost[1] = 8
next[1] = 2
🎯 Final DP Table
Nod Cost to Ne
e 7 xt
1 8 2
2 6 5
3 8 5
4 4 7
5 2 7
6 3 7
7 0 —
⭐ Minimum Cost Path
Start at node 1 and follow next[]:
1 → 2 → 5 → 7
Minimum cost = 8
