# Multistage Graph (Shortest Path) - GeeksforGeeks (2023)

C++ Java Python3 C# Javascript

A Multistage graph is a directed, weighted graph in which the nodes can be divided into a set of stages such that all edges are from a stage to next stage only (In other words there is no edge between vertices of same stage and from a vertex of current stage to previous stage).

The vertices of a multistage graph are divided into n number of disjoint subsets S = { S1 , S2 , S3 ……….. Sn }, where S1 is the source and Sn is the sink ( destination ). The cardinality of S1 and Sn are equal to 1. i.e., |S1| = |Sn| = 1.
We are given a multistage graph, a source and a destination, we need to find shortest path from source to destination. By convention, we consider source at stage 1 and destination as last stage.
Following is an example graph we will consider in this article :- Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Now there are various strategies we can apply :-

• The Brute force method of finding all possible paths between Source and Destination and then finding the minimum. That’s the WORST possible strategy.
• Dijkstra’s Algorithm of Single Source shortest paths. This method will find shortest paths from source to all other nodes which is not required in this case. So it will take a lot of time and it doesn’t even use the SPECIAL feature that this MULTI-STAGE graph has.
• Simple Greedy Method – At each node, choose the shortest outgoing path. If we apply this approach to the example graph given above we get the solution as 1 + 4 + 18 = 23. But a quick look at the graph will show much shorter paths available than 23. So the greedy method fails !
• The best option is Dynamic Programming. So we need to find Optimal Sub-structure, Recursive Equations and Overlapping Sub-problems.

Optimal Substructure and Recursive Equation :-
We define the notation :- M(x, y) as the minimum cost to T(target node) from Stage x, Node y.

`Shortest distance from stage 1, node 0 to destination, i.e., 7 is M(1, 0).// From 0, we can go to 1 or 2 or 3 to// reach 7. M(1, 0) = min(1 + M(2, 1), 2 + M(2, 2), 5 + M(2, 3))`

This means that our problem of 0 —> 7 is now sub-divided into 3 sub-problems :-

`So if we have total 'n' stages and targetas T, then the stopping condition  will be :-M(n-1, i) = i ---> T + M(n, T) = i ---> T`

Recursion Tree and Overlapping Sub-Problems:-
So, the hierarchy of M(x, y) evaluations will look something like this :-

`In M(i, j), i is stage number andj is node number M(1, 0) / | \ / | \ M(2, 1) M(2, 2) M(2, 3) / \ / \ / \M(3, 4) M(3, 5) M(3, 4) M(3, 5) M(3, 6) M(3, 6) . . . . . . . . . . . . . . . . . .`

So, here we have drawn a very small part of the Recursion Tree and we can already see Overlapping Sub-Problems. We can largely reduce the number of M(x, y) evaluations using Dynamic Programming.
Implementation details:
The below implementation assumes that nodes are numbered from 0 to N-1 from first stage (source) to last stage (destination). We also assume that the input graph is multistage.

We use top to bottom approach, and use dist[] array to store the value of overlapping sub-problem.

dist[i] will store the value of minimum distance from node i to node n-1 (target node).

Therefore, dist will store minimum distance between from source node to target node.

## C++

`// CPP program to find shortest distance`

`// in a multistage graph.`

`#include<bits/stdc++.h>`

`using` `namespace` `std;`

`#define N 8`

`#define INF INT_MAX`

`// Returns shortest distance from 0 to`

`// N-1.`

`int` `shortestDist(``int` `graph[N][N]) {`

`// dist[i] is going to store shortest`

`// distance from node i to node N-1.`

`int` `dist[N];`

`dist[N-1] = 0;`

`// Calculating shortest path for`

`// rest of the nodes`

`for` `(``int` `i = N-2 ; i >= 0 ; i--)`

`{`

`// Initialize distance from i to`

`// destination (N-1)`

`dist[i] = INF;`

`// Check all nodes of next stages`

`// to find shortest distance from`

`// i to N-1.`

`for` `(``int` `j = i ; j < N ; j++)`

`{`

`// Reject if no edge exists`

`if` `(graph[i][j] == INF)`

`continue``;`

`// We apply recursive equation to`

`// distance to target through j.`

`// and compare with minimum distance`

`// so far.`

`dist[i] = min(dist[i], graph[i][j] +`

`dist[j]);`

`}`

`}`

`return` `dist;`

`}`

`// Driver code`

`int` `main()`

`{`

`// Graph stored in the form of an`

`// adjacency Matrix`

`int` `graph[N][N] =`

`{{INF, 1, 2, 5, INF, INF, INF, INF},`

`{INF, INF, INF, INF, 4, 11, INF, INF},`

`{INF, INF, INF, INF, 9, 5, 16, INF},`

`{INF, INF, INF, INF, INF, INF, 2, INF},`

`{INF, INF, INF, INF, INF, INF, INF, 18},`

`{INF, INF, INF, INF, INF, INF, INF, 13},`

`{INF, INF, INF, INF, INF, INF, INF, 2},`

`{INF, INF, INF, INF, INF, INF, INF, INF}};`

`cout << shortestDist(graph);`

`return` `0;`

`}`

## Java

`// Java program to find shortest distance`

`// in a multistage graph.`

`import` `java.io.*;`

`import` `java.util.*;`

`class` `GFG {`

`static` `int` `N = ``8``;`

`static` `int` `INF = Integer.MAX_VALUE;`

`// Returns shortest distance from 0 to`

`// N-1.`

`public` `static` `int` `shortestDist(``int``[][] graph)`

`{`

`// dist[i] is going to store shortest`

`// distance from node i to node N-1.`

`int``[] dist = ``new` `int``[N];`

`dist[N - ``1``] = ``0``;`

`// Calculating shortest path for`

`// rest of the nodes`

`for` `(``int` `i = N - ``2``; i >= ``0``; i--) {`

`// Initialize distance from i to`

`// destination (N-1)`

`dist[i] = INF;`

`// Check all nodes of next stages`

`// to find shortest distance from`

`// i to N-1.`

`for` `(``int` `j = i; j < N; j++) {`

`// Reject if no edge exists`

`if` `(graph[i][j] == INF) {`

`continue``;`

`}`

`// We apply recursive equation to`

`// distance to target through j.`

`// and compare with minimum distance`

`// so far.`

`dist[i] = Math.min(dist[i],`

`graph[i][j] + dist[j]);`

`}`

`}`

`return` `dist[``0``];`

`}`

`// Driver code`

`public` `static` `void` `main(String[] args)`

`{`

`// Graph stored in the form of an`

`// adjacency Matrix`

`int``[][] graph = ``new` `int``[][] {`

`{ INF, ``1``, ``2``, ``5``, INF, INF, INF, INF },`

`{ INF, INF, INF, INF, ``4``, ``11``, INF, INF },`

`{ INF, INF, INF, INF, ``9``, ``5``, ``16``, INF },`

`{ INF, INF, INF, INF, INF, INF, ``2``, INF },`

`{ INF, INF, INF, INF, INF, INF, INF, ``18` `},`

`{ INF, INF, INF, INF, INF, INF, INF, ``13` `},`

`{ INF, INF, INF, INF, INF, INF, INF, ``2` `}`

`};`

`System.out.println(shortestDist(graph));`

`}`

`}`

`// This code has been contributed by 29AjayKumar`

## Python3

`# Python3 program to find shortest`

`# distance in a multistage graph.`

`# Returns shortest distance from`

`# 0 to N-1.`

`def` `shortestDist(graph):`

`global` `INF`

`# dist[i] is going to store shortest`

`# distance from node i to node N-1.`

`dist ``=` `[``0``] ``*` `N`

`dist[N ``-` `1``] ``=` `0`

`# Calculating shortest path`

`# for rest of the nodes`

`for` `i ``in` `range``(N ``-` `2``, ``-``1``, ``-``1``):`

`# Initialize distance from`

`# i to destination (N-1)`

`dist[i] ``=` `INF`

`# Check all nodes of next stages`

`# to find shortest distance from`

`# i to N-1.`

`for` `j ``in` `range``(N):`

`# Reject if no edge exists`

`if` `graph[i][j] ``=``=` `INF:`

`continue`

`# We apply recursive equation to`

`# distance to target through j.`

`# and compare with minimum`

`# distance so far.`

`dist[i] ``=` `min``(dist[i],`

`graph[i][j] ``+` `dist[j])`

`return` `dist[``0``]`

`# Driver code`

`N ``=` `8`

`INF ``=` `999999999999`

`# Graph stored in the form of an`

`# adjacency Matrix`

`graph ``=` `[[INF, ``1``, ``2``, ``5``, INF, INF, INF, INF],`

`[INF, INF, INF, INF, ``4``, ``11``, INF, INF],`

`[INF, INF, INF, INF, ``9``, ``5``, ``16``, INF],`

`[INF, INF, INF, INF, INF, INF, ``2``, INF],`

`[INF, INF, INF, INF, INF, INF, INF, ``18``],`

`[INF, INF, INF, INF, INF, INF, INF, ``13``],`

`[INF, INF, INF, INF, INF, INF, INF, ``2``]]`

`print``(shortestDist(graph))`

`# This code is contributed by PranchalK`

## C#

`// C# program to find shortest distance`

`// in a multistage graph.`

`using` `System;`

`class` `GFG`

`{`

`static` `int` `N = 8;`

`static` `int` `INF = ``int``.MaxValue;`

`// Returns shortest distance from 0 to`

`// N-1.`

`public` `static` `int` `shortestDist(``int``[,] graph) {`

`// dist[i] is going to store shortest`

`// distance from node i to node N-1.`

`int``[] dist = ``new` `int``[N];`

`dist[N-1] = 0;`

`// Calculating shortest path for`

`// rest of the nodes`

`for` `(``int` `i = N-2 ; i >= 0 ; i--)`

`{`

`// Initialize distance from i to`

`// destination (N-1)`

`dist[i] = INF;`

`// Check all nodes of next stages`

`// to find shortest distance from`

`// i to N-1.`

`for` `(``int` `j = i ; j < N ; j++)`

`{`

`// Reject if no edge exists`

`if` `(graph[i,j] == INF)`

`continue``;`

`// We apply recursive equation to`

`// distance to target through j.`

`// and compare with minimum distance`

`// so far.`

`dist[i] = Math.Min(dist[i], graph[i,j] +`

`dist[j]);`

`}`

`}`

`return` `dist;`

`}`

`// Driver code`

`static` `void` `Main()`

`{`

`// Graph stored in the form of an`

`// adjacency Matrix`

`int``[,] graph = ``new` `int``[,]`

`{{INF, 1, 2, 5, INF, INF, INF, INF},`

`{INF, INF, INF, INF, 4, 11, INF, INF},`

`{INF, INF, INF, INF, 9, 5, 16, INF},`

`{INF, INF, INF, INF, INF, INF, 2, INF},`

`{INF, INF, INF, INF, INF, INF, INF, 18},`

`{INF, INF, INF, INF, INF, INF, INF, 13},`

`{INF, INF, INF, INF, INF, INF, INF, 2}};`

`Console.Write(shortestDist(graph));`

`}`

`}`

`// This code is contributed by DrRoot_`

## Javascript

`<script>`

`// JavaScript program to find shortest distance`

`// in a multistage graph.`

`let N = 8;`

`let INF = Number.MAX_VALUE;`

`// Returns shortest distance from 0 to`

`// N-1.`

`function` `shortestDist(graph)`

`{`

`// dist[i] is going to store shortest`

`// distance from node i to node N-1.`

`let dist = ``new` `Array(N);`

`dist[N - 1] = 0;`

`// Calculating shortest path for`

`// rest of the nodes`

`for` `(let i = N - 2; i >= 0; i--)`

`{`

`// Initialize distance from i to`

`// destination (N-1)`

`dist[i] = INF;`

`// Check all nodes of next stages`

`// to find shortest distance from`

`// i to N-1.`

`for` `(let j = i; j < N; j++)`

`{`

`// Reject if no edge exists`

`if` `(graph[i][j] == INF)`

`{`

`continue``;`

`}`

`// We apply recursive equation to`

`// distance to target through j.`

`// and compare with minimum distance`

`// so far.`

`dist[i] = Math.min(dist[i], graph[i][j]`

`+ dist[j]);`

`}`

`}`

`return` `dist;`

`}`

`let graph = [[INF, 1, 2, 5, INF, INF, INF, INF],`

`[INF, INF, INF, INF, 4, 11, INF, INF],`

`[INF, INF, INF, INF, 9, 5, 16, INF],`

`[INF, INF, INF, INF, INF, INF, 2, INF],`

`[INF, INF, INF, INF, INF, INF, INF, 18],`

`[INF, INF, INF, INF, INF, INF, INF, 13],`

`[INF, INF, INF, INF, INF, INF, INF, 2]];`

`document.write(shortestDist(graph));`

`// This code is contributed by rag2127`

`</script>`

Output:

`9`

Time Complexity : O(n2)

My Personal Notesarrow_drop_up

Top Articles
Latest Posts
Article information

Author: Errol Quitzon

Last Updated: 02/14/2023

Views: 6475

Rating: 4.9 / 5 (59 voted)

Author information

Name: Errol Quitzon

Birthday: 1993-04-02

Address: 70604 Haley Lane, Port Weldonside, TN 99233-0942

Phone: +9665282866296

Job: Product Retail Agent

Hobby: Computer programming, Horseback riding, Hooping, Dance, Ice skating, Backpacking, Rafting

Introduction: My name is Errol Quitzon, I am a fair, cute, fancy, clean, attractive, sparkling, kind person who loves writing and wants to share my knowledge and understanding with you.