1.
Introduction
2.
What is the Multistage Graph?
3.
Problem Statement
4.
Example of Multistage Graph
4.1.
Step 1
4.2.
Step 2
4.3.
Step 3
4.4.
Step 4
4.5.
Step 5
5.
Dijkstra Algorithm
5.1.
Pseudocode
5.2.
Implementation of Multistage Graph
5.3.
Java
5.4.
C++
5.5.
Python
5.6.
C#
5.7.
Javascript
5.7.1.
Time Complexity
5.7.2.
Space Complexity
6.
DP Approach
6.1.
Algorithm
6.2.
Implementation of Multistage Graph
6.3.
C++
6.4.
Java
6.5.
Python
6.6.
C#
6.7.
Javascript
6.7.1.
Time Complexity
6.7.2.
Space Complexity
7.
7.1.
What is a multi-stage graph?
7.2.
What is the DP problem?
7.3.
What is the Multistage Algorithm in DAA?
7.4.
What is the Need of Dynamic Programming in a Multistage Graph?
7.5.
What is the Complexity of a Multistage Graph?
8.
Conclusion
Last Updated: Aug 24, 2024
Medium

# Multistage Graph(Shortest Path)

## Introduction

A multistage graph falls under the class of a directed and weighted graph. Here the vertices are divided into stages. The first and last stages will have a single vertex representing the starting or ending vertex. Also, between the starting and ending vertex, there will be vertices in different stages. Which will connect the starting and ending vertex.

The main aim of this graph is to find the minimum cost path between starting and ending vertex. This article will discuss the multistage graph and its implementation.

## What is the Multistage Graph?

A multistage graph is a directed graph where the nodes are divided into multiple stages, and edges only exist between nodes of consecutive stages. Each edge is assigned a weight representing the cost or distance associated with transitioning from one stage to the next. Multistage graphs are commonly used to model optimization problems involving a sequence of decisions or stages, where the goal is to minimize or maximize some objective function while traversing the graph from the initial stage to the final stage.

In a multistage graph, the first stage typically represents the initial state or starting point of the problem, while the last stage represents the final state or goal. Intermediate stages represent intermediate states or decision points where choices must be made to progress towards the final goal. The edges in the graph represent transitions between stages, and the weights on these edges represent the costs or benefits associated with making those transitions.

## Problem Statement

On the journey to Mordor to destroy the ring of power. Frodo along with you are going on a journey. You are chased by the knights of Saruman who wants to take the ring of power and gift it to Sauron. Frodo finds a map to Mordor and now it is on you to find the shortest path.

You are given a multistage graph on the map, a source (your current location) and a destination (Mordor). We need to find the shortest distance path from your current location to Mordor. For convention, we generally consider source at stage 1 and destination as the last stage.

Let’s see a sample example to understand the problem statement.

## Example of Multistage Graph

In the above graph, the cost of an edge is represented as c(i, j). We have to find the minimum cost path from vertex 1 to vertex 12. We will be using this below formula to find the shortest cost path from the source to the destination:

cost(i,j)=minimum{c(j,l)+cost(i+1,l)}

### Step 1

In Step 1, we use the forward approach (cost(5,12) = 0).

Here, 5 is the stage number and 12 is a node. Since there are no edges outgoing from vertex 12, the cost is 0.

### Step 2

Now, cost(4,9) = cost(9,12)= 6

cost(4,10) = cost(10,12)= 4

cost(4,11) = cost(11,12)= 2

### Step 3

cost(3,5) = minimum{cost(5,9)+cost(4,9),c(5,10)+cost(4,10)}

minimum{5+6,2+4}

minimum{11,6} = 6

cost(3,5) = 6

cost(3,6)=minimum{cost(6,10)+cost(4,10),cost(6,11)+cost(4,11)}

minimum{4+4,8+2}

minimum{8,10}=8

cost(3,6)=8

cost(3,7)=minimum{cost(7,9)+cost(4,9),cost(7,10)+cost(4,10),cost(7,11)+cost(4,11)} minimum{7+6,5+4,3+2}

minimum{13,9,5}=5

cost(3,7)=5

cost(3,8)=cost(8,11)+cost(4,11)=7+2=9 cost(3,8)=9

### Step 4

cost(2,2)=minimum{cost(2,5)+cost(3,5),cost(2,6)+cost(3,6),cost(2,7)+cost(3,7)} minimum{3+6,5+8,6+5}

minimum{9,13,11}=9

cost(2,2) = 9

cost(2,3)=minimum{c(3,6)+cost(3,6),cost(3,7)+cost(3,7),cost(3,8)+cost(3,8)} minimum{4+8,5+5,7+9}

minimum{12,10,16}=10

cost(2,3)=10

cost(2,4)=minimum{cost(4,7)+cost(3,7),cost(4,8)+cost(3,8)}

minimum{2+5,7+9}

minimum{7,16}=7

cost(2,4)=7

### Step 5

cost(1,1)=minimum{cost(1,2)+cost(2,2),cost(1,3)+cost(2,3),cost(1,4)+cost(2,4)} minimum{9+9,7+10,5+7}

minimum {18,17,12}=12

cost(1,1)=12

## Dijkstra Algorithm

Dijkstra's algorithm finds the shortest path between any two graph vertices.

It differs from the minimum spanning tree in that the shortest distance between two vertices may not include all of the graph's vertices.

### Pseudocode

``````function dijkstra(G, S)
for each vertex V in G
distance[V] <- infinite
previous[V] <- NULL
If V != S, add V to Priority Queue Q
distance[S] <- 0

while Q IS NOT EMPTY
U <- Extract MIN from Q
for each unvisited neighbour V of U
tempDistance <- distance[U] + edge_weight(U, V)
if tempDistance < distance[V]
distance[V] <- tempDistance
previous[V] <- U
return distance[], previous[]``````

• Java
• C++
• Python
• C#
• Javascript

### Java

``import java.util.ArrayList;import java.util.List;class Node {    char id;    Node previous;    int distanceFromStart = Integer.MAX_VALUE;    Node(char id) {        this.id = id;        Graph.nodes.add(this);    }}class Edge {    Node node1;    Node node2;    int distance;    Edge(Node node1, Node node2, int distance) {        this.node1 = node1;        this.node2 = node2;        this.distance = distance;        Graph.edges.add(this);    }    boolean connects(Node node1, Node node2) {        return (this.node1 == node1 && this.node2 == node2) ||               (this.node1 == node2 && this.node2 == node1);    }}class Graph {    static List<Node> nodes = new ArrayList<>();    static List<Edge> edges = new ArrayList<>();    static void dijkstras() {        while (!nodes.isEmpty()) {            Node smallest = extractSmallest();            List<Node> adjacentNodes = adjacentRemainingNodes(smallest);            for (Node adjacent : adjacentNodes) {                int distance = distance(smallest, adjacent) + smallest.distanceFromStart;                if (distance < adjacent.distanceFromStart) {                    adjacent.distanceFromStart = distance;                    adjacent.previous = smallest;                }            }        }    }    static Node extractSmallest() {        if (nodes.isEmpty()) return null;        Node smallest = nodes.get(0);        for (Node node : nodes) {            if (node.distanceFromStart < smallest.distanceFromStart) {                smallest = node;            }        }        nodes.remove(smallest);        return smallest;    }    static List<Node> adjacentRemainingNodes(Node node) {        List<Node> adjacentNodes = new ArrayList<>();        for (Edge edge : edges) {            Node adjacent = null;            if (edge.node1 == node) {                adjacent = edge.node2;            } else if (edge.node2 == node) {                adjacent = edge.node1;            }            if (adjacent != null && nodes.contains(adjacent)) {                adjacentNodes.add(adjacent);            }        }        return adjacentNodes;    }    static int distance(Node node1, Node node2) {        for (Edge edge : edges) {            if (edge.connects(node1, node2)) {                return edge.distance;            }        }        return -1; // Should never happen    }    static void printShortestRouteTo(Node destination) {        System.out.println("Distance from start: " + destination.distanceFromStart);    }    public static void main(String[] args) {        Node a = new Node('a');        Node b = new Node('b');        Node c = new Node('c');        Node d = new Node('d');        Node e = new Node('e');        Node f = new Node('f');        Node g = new Node('g');        new Edge(a, c, 1);        new Edge(a, d, 2);        new Edge(b, c, 2);        new Edge(c, d, 1);        new Edge(b, f, 3);        new Edge(c, e, 3);        new Edge(e, f, 2);        new Edge(d, g, 1);        new Edge(g, f, 1);        a.distanceFromStart = 0; // set start node        dijkstras();        printShortestRouteTo(f);    }}``

### C++

``#include <iostream>#include <vector>#define INT_MAX 10000000using namespace std;void DijkstrasTest();int main() {	  DijkstrasTest();	  return 0;}class Node;class Edge;void Dijkstras();	vector<Node*>* AdjacentRemainingNodes(Node* node);	Node* ExtractSmallest(vector<Node*>& nodes);	int Distance(Node* node1, Node* node2);	bool Contains(vector<Node*>& nodes, Node* node);	void PrintShortestRouteTo(Node* destination);vector<Node*> nodes;vector<Edge*> edges;class Node {   public:	  Node(char id)	    : id(id), previous(NULL), distanceFromStart(INT_MAX) {	    nodes.push_back(this);  }   public:	  char id;	  Node* previous;	  int distanceFromStart;};class Edge {   public:  Edge(Node* node1, Node* node2, int distance)    : node1(node1), node2(node2), distance(distance) {    edges.push_back(this);  }  bool Connects(Node* node1, Node* node2) {    return (      (node1 == this->node1 &&       node2 == this->node2) ||      (node1 == this->node2 &&       node2 == this->node1));  }   public:	  Node* node1;	  Node* node2;	  int distance;};void DijkstrasTest() {	  Node* a = new Node('a');	  Node* b = new Node('b');	  Node* c = new Node('c');	  Node* d = new Node('d');	  Node* e = new Node('e');	  Node* f = new Node('f');	  Node* g = new Node('g'); 	 Edge* e1 = new Edge(a, c, 1);	 Edge* e2 = new Edge(a, d, 2); 	 Edge* e3 = new Edge(b, c, 2); 	 Edge* e4 = new Edge(c, d, 1); 	 Edge* e5 = new Edge(b, f, 3); 	 Edge* e6 = new Edge(c, e, 3); 	 Edge* e7 = new Edge(e, f, 2); 	 Edge* e8 = new Edge(d, g, 1); 	 Edge* e9 = new Edge(g, f, 1);		  a->distanceFromStart = 0;  // set start node		  Dijkstras();		  PrintShortestRouteTo(f);}void Dijkstras() {	  while (nodes.size() > 0) 	  {    	Node* smallest = ExtractSmallest(nodes);    	vector<Node*>* adjacentNodes =    	  AdjacentRemainingNodes(smallest);	    const int size = adjacentNodes->size();	    for (int i = 0; i < size; ++i) 	    {	      Node* adjacent = adjacentNodes->at(i);	      int distance = Distance(smallest, adjacent) +    	           smallest->distanceFromStart;	      if (distance < adjacent->distanceFromStart) 	      {    	    adjacent->distanceFromStart = distance;    	    adjacent->previous = smallest;    	  }    	}   	 delete adjacentNodes;  	}}// Find the node with the smallest distance,// remove it, and return it.Node* ExtractSmallest(vector<Node*>& nodes) {	  int size = nodes.size();	  if (size == 0) return NULL;	  int smallestPosition = 0;	  Node* smallest = nodes.at(0);	  for (int i = 1; i < size; ++i) 	  {	    Node* current = nodes.at(i);    	if (current->distanceFromStart <    	  smallest->distanceFromStart)     	  {    	  smallest = current;    	  smallestPosition = i;   		  }  	   }  	nodes.erase(nodes.begin() + smallestPosition);  	return smallest;}// Return all nodes adjacent to 'node' which are still// in the 'nodes' collection.vector<Node*>* AdjacentRemainingNodes(Node* node) {  vector<Node*>* adjacentNodes = new vector<Node*>();  const int size = edges.size();  for (int i = 0; i < size; ++i)   {    Edge* edge = edges.at(i);    Node* adjacent = NULL;    if (edge->node1 == node)     {      adjacent = edge->node2;    }     else if (edge->node2 == node)    {      adjacent = edge->node1;    }    if (adjacent && Contains(nodes, adjacent))     {      adjacentNodes->push_back(adjacent);    }  }  return adjacentNodes;}// Return distance between two connected nodesint Distance(Node* node1, Node* node2) {  const int size = edges.size();  for (int i = 0; i < size; ++i)   {    Edge* edge = edges.at(i);    if (edge->Connects(node1, node2))     {      return edge->distance;    }  }  return -1;  // should never happen}// Does the 'nodes' vector contain 'node'bool Contains(vector<Node*>& nodes, Node* node) {  const int size = nodes.size();  for (int i = 0; i < size; ++i)   {    if (node == nodes.at(i))     {      return true;    }  }  return false;}void PrintShortestRouteTo(Node* destination) {  Node* previous = destination;  cout << "Distance from start: "     << destination->distanceFromStart << endl;  cout << endl;}// these two not neededvector<Edge*>* AdjacentEdges(vector<Edge*>& Edges, Node* node);void RemoveEdge(vector<Edge*>& Edges, Edge* edge);vector<Edge*>* AdjacentEdges(vector<Edge*>& edges, Node* node) {  vector<Edge*>* adjacentEdges = new vector<Edge*>();  const int size = edges.size();  for (int i = 0; i < size; ++i)   {    Edge* edge = edges.at(i);    if (edge->node1 == node)     {      cout << "adjacent: " << edge->node2->id << endl;      adjacentEdges->push_back(edge);    } else if (edge->node2 == node)     {      cout << "adjacent: " << edge->node1->id << endl;      adjacentEdges->push_back(edge);    }  }  return adjacentEdges;}void RemoveEdge(vector<Edge*>& edges, Edge* edge) {  vector<Edge*>::iterator it;  for (it = edges.begin(); it < edges.end(); ++it) {    if (*it == edge) {      edges.erase(it);      return;    }  }}``

### Python

``class Node:    def __init__(self, id):        self.id = id        self.previous = None        self.distance_from_start = float('inf')        Graph.nodes.append(self)class Edge:    def __init__(self, node1, node2, distance):        self.node1 = node1        self.node2 = node2        self.distance = distance        Graph.edges.append(self)    def connects(self, node1, node2):        return (self.node1 == node1 and self.node2 == node2) or \               (self.node1 == node2 and self.node2 == node1)class Graph:    nodes = []    edges = []    @staticmethod    def dijkstras():        while Graph.nodes:            smallest = Graph.extract_smallest()            adjacent_nodes = Graph.adjacent_remaining_nodes(smallest)            for adjacent in adjacent_nodes:                dist = Graph.distance(smallest, adjacent) + smallest.distance_from_start                if dist < adjacent.distance_from_start:                    adjacent.distance_from_start = dist                    adjacent.previous = smallest    @staticmethod    def extract_smallest():        smallest = min(Graph.nodes, key=lambda node: node.distance_from_start, default=None)        Graph.nodes.remove(smallest)        return smallest    @staticmethod    def adjacent_remaining_nodes(node):        adjacent_nodes = []        for edge in Graph.edges:            adjacent = None            if edge.node1 == node:                adjacent = edge.node2            elif edge.node2 == node:                adjacent = edge.node1            if adjacent and adjacent in Graph.nodes:                adjacent_nodes.append(adjacent)        return adjacent_nodes    @staticmethod    def distance(node1, node2):        for edge in Graph.edges:            if edge.connects(node1, node2):                return edge.distance        return -1  # Should never happen    @staticmethod    def print_shortest_route_to(destination):        print("Distance from start: {}".format(destination.distance_from_start))def main():    a = Node('a')    b = Node('b')    c = Node('c')    d = Node('d')    e = Node('e')    f = Node('f')    g = Node('g')    Edge(a, c, 1)    Edge(a, d, 2)    Edge(b, c, 2)    Edge(c, d, 1)    Edge(b, f, 3)    Edge(c, e, 3)    Edge(e, f, 2)    Edge(d, g, 1)    Edge(g, f, 1)    a.distance_from_start = 0  # set start node    Graph.dijkstras()    Graph.print_shortest_route_to(f)if __name__ == "__main__":    main()``

### C#

``using System;using System.Collections.Generic;using System.Linq;public class Node {    public char Id;    public Node Previous;    public int DistanceFromStart = int.MaxValue;    public Node(char id) {        Id = id;        Graph.Nodes.Add(this);    }}public class Edge {    public Node Node1;    public Node Node2;    public int Distance;    public Edge(Node node1, Node node2, int distance) {        Node1 = node1;        Node2 = node2;        Distance = distance;        Graph.Edges.Add(this);    }    public bool Connects(Node node1, Node node2) {        return (Node1 == node1 && Node2 == node2) || (Node1 == node2 && Node2 == node1);    }}public static class Graph {    public static List<Node> Nodes = new List<Node>();    public static List<Edge> Edges = new List<Edge>();    public static void Dijkstras() {        while (Nodes.Count > 0) {            Node smallest = ExtractSmallest();            List<Node> adjacentNodes = AdjacentRemainingNodes(smallest);            foreach (Node adjacent in adjacentNodes) {                int distance = Distance(smallest, adjacent) + smallest.DistanceFromStart;                if (distance < adjacent.DistanceFromStart) {                    adjacent.DistanceFromStart = distance;                    adjacent.Previous = smallest;                }            }        }    }    private static Node ExtractSmallest() {        Node smallest = Nodes.OrderBy(n => n.DistanceFromStart).FirstOrDefault();        Nodes.Remove(smallest);        return smallest;    }    private static List<Node> AdjacentRemainingNodes(Node node) {        List<Node> adjacentNodes = new List<Node>();        foreach (Edge edge in Edges) {            Node adjacent = null;            if (edge.Node1 == node) {                adjacent = edge.Node2;            } else if (edge.Node2 == node) {                adjacent = edge.Node1;            }            if (adjacent != null && Nodes.Contains(adjacent)) {                adjacentNodes.Add(adjacent);            }        }        return adjacentNodes;    }    private static int Distance(Node node1, Node node2) {        foreach (Edge edge in Edges) {            if (edge.Connects(node1, node2)) {                return edge.Distance;            }        }        return -1; // Should never happen    }    public static void PrintShortestRouteTo(Node destination) {        Console.WriteLine(\$"Distance from start: {destination.DistanceFromStart}");    }}class Program {    static void Main() {        Node a = new Node('a');        Node b = new Node('b');        Node c = new Node('c');        Node d = new Node('d');        Node e = new Node('e');        Node f = new Node('f');        Node g = new Node('g');        new Edge(a, c, 1);        new Edge(a, d, 2);        new Edge(b, c, 2);        new Edge(c, d, 1);        new Edge(b, f, 3);        new Edge(c, e, 3);        new Edge(e, f, 2);        new Edge(d, g, 1);        new Edge(g, f, 1);        a.DistanceFromStart = 0; // set start node        Graph.Dijkstras();        Graph.PrintShortestRouteTo(f);    }}``

### Javascript

``class Node {    constructor(id) {        this.id = id;        this.previous = null;        this.distanceFromStart = Infinity;        Graph.nodes.push(this);    }}class Edge {    constructor(node1, node2, distance) {        this.node1 = node1;        this.node2 = node2;        this.distance = distance;        Graph.edges.push(this);    }    connects(node1, node2) {        return (this.node1 === node1 && this.node2 === node2) ||                (this.node1 === node2 && this.node2 === node1);    }}class Graph {    static nodes = [];    static edges = [];    static dijkstras() {        while (Graph.nodes.length > 0) {            let smallest = Graph.extractSmallest();            let adjacentNodes = Graph.adjacentRemainingNodes(smallest);            adjacentNodes.forEach(adjacent => {                let distance = Graph.distance(smallest, adjacent) + smallest.distanceFromStart;                if (distance < adjacent.distanceFromStart) {                    adjacent.distanceFromStart = distance;                    adjacent.previous = smallest;                }            });        }    }    static extractSmallest() {        let smallest = Graph.nodes.reduce((min, node) => node.distanceFromStart < min.distanceFromStart ? node : min, Graph.nodes[0]);        Graph.nodes = Graph.nodes.filter(node => node !== smallest);        return smallest;    }    static adjacentRemainingNodes(node) {        let adjacentNodes = [];        Graph.edges.forEach(edge => {            let adjacent = null;            if (edge.node1 === node) {                adjacent = edge.node2;            } else if (edge.node2 === node) {                adjacent = edge.node1;            }            if (adjacent && Graph.nodes.includes(adjacent)) {                adjacentNodes.push(adjacent);            }        });        return adjacentNodes;    }    static distance(node1, node2) {        let edge = Graph.edges.find(edge => edge.connects(node1, node2));        return edge ? edge.distance : -1; // Should never happen    }    static printShortestRouteTo(destination) {        console.log(`Distance from start: \${destination.distanceFromStart}`);    }}function main() {    let a = new Node('a');    let b = new Node('b');    let c = new Node('c');    let d = new Node('d');    let e = new Node('e');    let f = new Node('f');    let g = new Node('g');    new Edge(a, c, 1);    new Edge(a, d, 2);    new Edge(b, c, 2);    new Edge(c, d, 1);    new Edge(b, f, 3);    new Edge(c, e, 3);    new Edge(e, f, 2);    new Edge(d, g, 1);    new Edge(g, f, 1);    a.distanceFromStart = 0; // set start node    Graph.dijkstras();    Graph.printShortestRouteTo(f);}main();``

Output:

#### Time Complexity

The time complexity of the algorithm used is O(V2). Here, V is the number of vertices. As we are using adjacency matrix representation. This time complexity of the approach is O(V2)

#### Space Complexity

The space complexity of the algorithm used is O(V). The adjacency list and min heap required O(V) spaces. That is why the space complexity of the approach is O(V).

## DP Approach

As Dijkstra algorithm may not include all of the graph's vertices. We use a dynamic programming approach to solve this problem. The Dijkstra method did find the shortest paths from the source to all other nodes which were not required in our case. So it did take a lot of time. And it didn’t use the feature that the MULTI-STAGE graph has.

We will now use a dynamic programming approach. Here we will use optimal sub-structure, recursive equations and overlapping sub-problems to find the optimal solution to the multistage graph problem.

### Algorithm

1. We will start by assuming that nodes are numbered from 0 to N-1 from the first stage (source) to the last stage (destination) of the graph.
2. We can also assume that the input graph is a multistage graph.
3. We use the top to bottom approach and use the distance[] array to store the value of overlapping sub-problem.
4. The distance[i] array will store the value of the minimum distance from node i to node n-1 (target node).
5. Therefore, distance[0] will store the minimum distance between from source node and to target node.

• C++
• Java
• Python
• C#
• Javascript

### C++

``#include<bits/stdc++.h>using namespace std;#define N 8#define DIS INT_MAX// Function which will returns shortest distance from 0 to N-1.int shortestDistance(int graph[N][N]) {	// distance from node i to node N-1.	int distance[N];	distance[N-1] = 0;	// Calculating the shortest path for rest nodes		for (int i = N-2 ; i >= 0 ; i--)		{		// Initialize the distance from i to the destination (N-1)			distance[i] = DIS;					//Now check all nodes of next stages to find the shortest distance from i to N-1.			for (int j = i ; j < N ; j++)			{		// Reject the nodes if no edge exists				if (graph[i][j] == DIS)				continue;		// We now apply recursive equation to find the distance to target through j.			distance[i] = min(distance[i], graph[i][j] + distance[j]);			}		}	return distance[0];}//--------------------------------Main Function-------------------------------------//int main(){	int graph[N][N] =		{{DIS, 1, 2, 5, DIS, DIS, DIS, DIS},		{DIS, DIS, DIS, DIS, 4, 11, DIS, DIS},		{DIS, DIS, DIS, DIS, 9, 5, 16, DIS},		{DIS, DIS, DIS, DIS, DIS, DIS, 2, DIS},		{DIS, DIS, DIS, DIS, DIS, DIS, DIS, 18},		{DIS, DIS, DIS, DIS, DIS, DIS, DIS, 13},		{DIS, DIS, DIS, DIS, DIS, DIS, DIS, 2},		{DIS, DIS, DIS, DIS, DIS, DIS, DIS, DIS}};	cout <<"Distance from start: "<< shortestDistance(graph);	return 0;}``

### Java

``public class ShortestPath {    static final int N = 8;    static final int DIS = Integer.MAX_VALUE;    static int shortestDistance(int[][] graph) {        int[] distance = new int[N];        distance[N-1] = 0; // Destination is N-1        for (int i = N-2; i >= 0; i--) {            distance[i] = DIS;            for (int j = i; j < N; j++) {                if (graph[i][j] == DIS) continue;                distance[i] = Math.min(distance[i], graph[i][j] + distance[j]);            }        }        return distance[0];    }    public static void main(String[] args) {        int[][] graph = {            {DIS, 1, 2, 5, DIS, DIS, DIS, DIS},            {DIS, DIS, DIS, DIS, 4, 11, DIS, DIS},            {DIS, DIS, DIS, DIS, 9, 5, 16, DIS},            {DIS, DIS, DIS, DIS, DIS, DIS, 2, DIS},            {DIS, DIS, DIS, DIS, DIS, DIS, DIS, 18},            {DIS, DIS, DIS, DIS, DIS, DIS, DIS, 13},            {DIS, DIS, DIS, DIS, DIS, DIS, DIS, 2},            {DIS, DIS, DIS, DIS, DIS, DIS, DIS, DIS}        };        System.out.println("Distance from start: " + shortestDistance(graph));    }}``

### Python

``N = 8DIS = float('inf')def shortest_distance(graph):    distance = [0] * N    distance[N-1] = 0  # Destination is N-1    for i in range(N-2, -1, -1):        distance[i] = DIS        for j in range(i, N):            if graph[i][j] == DIS:                continue            distance[i] = min(distance[i], graph[i][j] + distance[j])    return distance[0]graph = [    [DIS, 1, 2, 5, DIS, DIS, DIS, DIS],    [DIS, DIS, DIS, DIS, 4, 11, DIS, DIS],    [DIS, DIS, DIS, DIS, 9, 5, 16, DIS],    [DIS, DIS, DIS, DIS, DIS, DIS, 2, DIS],    [DIS, DIS, DIS, DIS, DIS, DIS, DIS, 18],    [DIS, DIS, DIS, DIS, DIS, DIS, DIS, 13],    [DIS, DIS, DIS, DIS, DIS, DIS, DIS, 2],    [DIS, DIS, DIS, DIS, DIS, DIS, DIS, DIS]]print("Distance from start:", shortest_distance(graph))``

### C#

``using System;public class ShortestPath {    const int N = 8;    const int DIS = int.MaxValue;    static int ShortestDistance(int[,] graph) {        int[] distance = new int[N];        distance[N-1] = 0; // Destination is N-1        for (int i = N-2; i >= 0; i--) {            distance[i] = DIS;            for (int j = i; j < N; j++) {                if (graph[i, j] == DIS) continue;                distance[i] = Math.Min(distance[i], graph[i, j] + distance[j]);            }        }        return distance[0];    }    public static void Main() {        int[,] graph = {            {DIS, 1, 2, 5, DIS, DIS, DIS, DIS},            {DIS, DIS, DIS, DIS, 4, 11, DIS, DIS},            {DIS, DIS, DIS, DIS, 9, 5, 16, DIS},            {DIS, DIS, DIS, DIS, DIS, DIS, 2, DIS},            {DIS, DIS, DIS, DIS, DIS, DIS, DIS, 18},            {DIS, DIS, DIS, DIS, DIS, DIS, DIS, 13},            {DIS, DIS, DIS, DIS, DIS, DIS, DIS, 2},            {DIS, DIS, DIS, DIS, DIS, DIS, DIS, DIS}        };        Console.WriteLine("Distance from start: " + ShortestDistance(graph));    }}``

### Javascript

``const N = 8;const DIS = Infinity;function shortestDistance(graph) {    const distance = Array(N).fill(DIS);    distance[N-1] = 0; // Destination is N-1    for (let i = N-2; i >= 0; i--) {        for (let j = i; j < N; j++) {            if (graph[i][j] === DIS) continue;            distance[i] = Math.min(distance[i], graph[i][j] + distance[j]);        }    }    return distance[0];}const graph = [    [DIS, 1, 2, 5, DIS, DIS, DIS, DIS],    [DIS, DIS, DIS, DIS, 4, 11, DIS, DIS],    [DIS, DIS, DIS, DIS, 9, 5, 16, DIS],    [DIS, DIS, DIS, DIS, DIS, DIS, 2, DIS],    [DIS, DIS, DIS, DIS, DIS, DIS, DIS, 18],    [DIS, DIS, DIS, DIS, DIS, DIS, DIS, 13],    [DIS, DIS, DIS, DIS, DIS, DIS, DIS, 2],    [DIS, DIS, DIS, DIS, DIS, DIS, DIS, DIS]];console.log("Distance from start: " + shortestDistance(graph));``

Output:

``Distance from Start: 9``

#### Time Complexity

The time complexity of the above-used algorithm is O(n2). Here, n is the number of nodes in the graph. We are traversing the graph using the top to bottom approach and the distance array to store the value of overlapping sub-problems. The time complexity is O(n2).

#### Space Complexity

The space complexity of the above-used algorithm is O(E). Here, E is the length of the edge. We are using the distance array to store the value of overlapping sub-problems.

### What is a multi-stage graph?

A multistage graph is a type of directed and weighted graph. Here, the nodes are divided into stages and all edges are directed from one stage to the next.

### What is the DP problem?

The DP is a method for problem-solving. It is done by breaking the problem into a collection of subproblems. We only solve each of these subproblems once and then we store their solutions.

### What is the Multistage Algorithm in DAA?

The multistage algorithm in Design and Analysis of Algorithms (DAA) is a dynamic programming approach used to solve optimization problems represented by multistage graphs. It efficiently finds the optimal solution by iteratively evaluating all possible paths through the graph.

### What is the Need of Dynamic Programming in a Multistage Graph?

Dynamic programming is needed in a multistage graph to efficiently solve optimization problems by breaking them down into smaller subproblems and solving them recursively. By storing and reusing the solutions to subproblems, dynamic programming avoids redundant computations and significantly improves the efficiency of solving multistage graph problems.

### What is the Complexity of a Multistage Graph?

The complexity of a multistage graph problem solved using dynamic programming depends on the number of stages and the number of nodes in each stage. In general, the time complexity is polynomial, often represented as O(n^2), where n is the total number of nodes in the multistage graph. This makes multistage graph problems solvable in polynomial time, making dynamic programming an efficient approach for optimization.

## Conclusion

This article briefly discussed the Multistage Graph (Shortest Path). Multistage graphs offer a powerful framework for modeling and solving optimization problems involving sequential decision-making processes. By dividing the problem into stages and representing transitions between stages with edges, multistage graphs provide a structured approach to finding the shortest path through a sequence of interconnected stages.

If you wish to learn more, you can also check out our articles

You can also refer to our guided path on the basics of Java and many more on our Website.

Refer to our Guided Path on Code360 to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScript, and many more! If you wish to test your competency in coding, you may check out the mock test series

But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problemsinterview experiences, and interview bundles for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Live masterclass