Multistage Graph (Shortest Path)

A multistage graph is a directed, weighted graph whose vertices split into ordered stages, with edges only ever pointing from one stage to the next. There is a single source in the first stage and a single sink in the last. The classic question: what is the cheapest path from source to sink? Because of the layered structure, we can solve it with a clean right-to-left dynamic program — no Dijkstra needed.

The slow way first

You could enumerate every source-to-sink path and take the minimum. But the number of paths grows multiplicatively with the number of stages — two choices per stage over k stages is already 2^k paths. That is exponential and re-walks the same tail of the graph over and over.

The question to ask: what does an answer for one node depend on? The cheapest way out of a node depends only on the cheapest way out of the nodes one stage to its right. If those are already solved, each node is a single min.

The idea: solve stages from the back

Define cost[u] = the cheapest cost to get from u all the way to the sink. The sink reaches itself for free, so cost[sink] = 0. For any other node, every outgoing edge leads into the next stage, which we have already solved — so:

cost[u] = min over edges (u → v, weight w) of (w + cost[v])

Process the stages right to left. By the time we reach a node, the costs of all its successors are known.

The source is the very last node we solve, and cost[source] is the answer.

Walk through it

Step through the animation. We light up the sink T first (cost = 0), then move one stage left at a time. C and D each have a single edge to T, so their costs are just the edge weights. Then A and B each compare their two outgoing options and keep the smaller. Finally S compares S→A (total 9) against S→B (total 7) and picks 7. Following the cheaper choices back out spells the path S→B→D→T.

Pseudocode

cost[sink] = 0
for each node u, going stage by stage from the last stage back to the source:
    cost[u] = +infinity
    for each outgoing edge u -> v with weight w:
        cost[u] = min(cost[u], w + cost[v])   # v is one stage ahead, already solved
return cost[source]

The Python solution

def shortest(graph, src, sink):
    cost = {}
    # last stage costs nothing to reach the sink
    cost[sink] = 0
    for u in reversed(order):       # right to left
        cost[u] = min(w + cost[v]
                      for v, w in graph[u])
    return cost[src]

• cost maps each node to its cheapest distance to the sink.
• cost[sink] = 0 seeds the recurrence — the last stage is free to reach from itself.
• order is the nodes listed source-first; reversed(order) walks them from the last stage back, so every successor is solved before the node that needs it.
• graph[u] lists u's outgoing edges as (v, w) pairs; the generator builds w + cost[v] for each and min keeps the smallest.
• cost[src] is the final answer once the source is processed.

Complexity

We touch every edge exactly once and store one cost per node, so the work is linear in the size of the graph — a huge win over enumerating paths.

When this pattern shows up

Practice