# Multistage Graph Problem using Dynamic Programming

## Multistage Graph

Multistage Graph problem is defined as follow:

- Multistage graph G = (V, E, W) is a weighted directed graph in which vertices are partitioned into k ≥ 2 disjoint sub sets V = {V
_{1}, V_{2}, …, V_{k}} such that if edge (u, v) is present in E then u ∈ V_{i}and v ∈ V_{i+1}, 1 ≤ i ≤ k. The goal of multistage graph problem is to find minimum cost path from source to destination vertex. - The input to the algorithm is a k-stage graph, n vertices are indexed in increasing order of stages.
- The algorithm operates in the backward direction, i.e. it starts from the last vertex of the graph and proceeds in a backward direction to find minimum cost path.
- Minimum cost of vertex j ∈ V
_{i}from vertex r ∈ V_{i+1}is defined as,

Cost[j] = min{ c[j, r] + cost[r] }

where, c[j, r] is the weight of edge <j, r> and cost[r] is the cost of moving from end vertex to vertex r.

- Algorithm for the multistage graph is described below :

## Algorithm for Multistage Graph

**Algorithm **MULTI_STAGE(G, k, n, p)
// Description: Solve multi-stage problem using dynamic programming
// Input:
k: Number of stages in graph G = (V, E)
c[i, j]:Cost of edge (i, j)
// Output: p[1:k]:Minimum cost path
cost[n] ← 0
**for **j ← n – 1 to 1 **do**
//Let r be a vertex such that (j, r) in E and c[j, r] + cost[r] is minimum
cost[j] ← c[j, r] + cost[r]
π[j] ← r
**end**
//Find minimum cost path
p[1] ← 1
p[k] ← n
**for **j ← 2 to k - 1 **do**
p[j] ← π[p[j - 1]]
**end**

## Complexity Analysis of Multistage Graph

If graph G has |E| edges, then cost computation time would be O(n + |E|). The complexity of tracing the minimum cost path would be O(k), k < n. Thus total time complexity of multistage graph using dynamic programming would be O(n + |E|).

## Example

**Example: Find minimum path cost between vertex s and t for following multistage graph using dynamic programming.**

**Solution:**

Solution to multistage graph using dynamic programming is constructed as,

Cost[j] = min{c[j, r] + cost[r]}

Here, number of stages k = 5, number of vertices n = 12, source s = 1 and target t = 12

Initialization:

Cost[n] = 0 ⇒ Cost[12] = 0.

p[1] = s ⇒ p[1] = 1

p[k] = t ⇒ p[5] = 12.

r = t = 12.

**Stage 4:**

**Stage 3:**

*Vertex 6 is connected to vertices 9 and 10*:

Cost[6] = min{ c[6, 10] + Cost[10], c[6, 9] + Cost[9] }

= min{5 + 2, 6 + 4} = min{7, 10} = 7

p[6] = 10

*Vertex 7 is connected to vertices 9 and 10*:

Cost[7] = min{ c[7, 10] + Cost[10], c[7, 9] + Cost[9] }

= min{3 + 2, 4 + 4} = min{5, 8} = 5

p[7] = 10

*Vertex 8 is connected to vertex 10 and 11*:

Cost[8] = min{ c[8, 11] + Cost[11], c[8, 10] + Cost[10] }

= min{6 + 5, 5 + 2} = min{11, 7} = 7 p[8] = 10

**Stage 2:**

*Vertex 2 is connected to vertices6, 7 and 8:*

Cost[2] = min{ c[2, 6] + Cost[6], c[2, 7] + Cost[7], c[2, 8] + Cost[8] }

= min{4 + 7, 2 + 5, 1 + 7} = min{11, 7, 8} = 7

p[2] = 7

*Vertex 3 is connected to vertices 6and 7:*

Cost[3] = min{ c[3, 6] + Cost[6], c[3, 7] + Cost[7] }

= min{2 + 7, 7 + 5} = min{9, 12} = 9

p[3] = 6

*Vertex 4 is connected to vertex 8:*

Cost[4] = c[4, 8] + Cost[8] = 11 + 7 = 18

p[4] = 8

*Vertex 5 is connected to vertices 7 and 8:*

Cost[5] = min{ c[5, 7] + Cost[7], c[5, 8] + Cost[8] }

= min{11 + 5, 8 + 7} = min{16, 15} = 15 p[5] = 8

**Stage 1:**

*Vertex 1 is connected to vertices 2, 3, 4 and 5:*

Cost[1] = min{ c[1, 2] + Cost[2], c[1, 3] + Cost[3], c[1, 4] + Cost[4], c[1, 5] + Cost[5]}

= min{ 9 + 7, 7 + 9, 3 + 18, 2 + 15 }

= min { 16, 16, 21, 17 } = 16 p[1] = 2

**Trace the solution:**

p[1] = 2

p[2] = 7

p[7] = 10

p[10] = 12

Minimum cost path is : 1 – 2 – 7 – 10 – 12

Cost of the path is : 9 + 2 + 3 + 2 = 16

## Some Popular Problems Solved using Dynamic Programming

- Binomial Coefficient
- Making a Change
- Knapsack Problem
- Multistate Graph Problem
- Optimal Binary Search Tree
- Matrix Chain Multiplication
- Longest Common Subsequence
- Bellman-Ford (Single Source Shortest Path) Algorithm
- Floyd-Warshall (All Pair Shortest Path) Problem
- Assembly Line Scheduling
- Travelling Salseman Problem
- Flow Shop Scheduling

Additional Reading: Read a research article