Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is the Multistage Graph?
3.
Problem Statement
4.
Example
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 
5.3.
C++
5.3.1.
Time Complexity
5.3.2.
Space Complexity
6.
DP Approach 
6.1.
Algorithm
6.2.
Implementation 
6.3.
C++
6.3.1.
Time Complexity
6.3.2.
Space Complexity
7.
Frequently Asked Questions
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: May 19, 2024
Medium

Multistage Graph

Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

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. 

introduction

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.

Multistage Graph

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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.

Problem Statement

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

Example

Multistage graph example

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[]

Implementation 

  • C++

C++

#include <iostream>
#include <vector>

#define INT_MAX 10000000
using 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 nodes
int 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 needed
vector<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;
   }
 }
}

Output:

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.

Implementation 

  • C++

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;
}

Output:

output

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.

Read more about C Programming here.

Frequently Asked Questions

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 Convert BST to the Greatest Sum TreeInbuilt binary search in different languageswhy binary heap is better than BST for priority queueCheck Identical TreesShortest Path In Binary MatrixBoundary Traversal of Binary Tree, and self-balancing BST. 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. You can also participate in the contests hosted on Coding Ninjas Studio!

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!

Happy learning!

Previous article
Erdos RenyI Model for generating random graphs
Next article
Minimize the Number of Weakly Connected Nodes
Live masterclass