Multistage Graph Problem using Dynamic Programming

by codecrucks · Published 25/11/2021 · Updated 03/08/2022

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₁, V₂, …, 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

Multistage Graph using dynamic programming

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

Additional Reading: Read a research article

Multistage Graph Problem using Dynamic Programming