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.

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.

Letâ€™s see a sample example to understand the problem statement.

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.

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

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

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

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:

Time Complexity

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

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

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.

We can also assume that the input graph is a multistage graph.

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

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

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() {

cout <<"Distance from start: "<< shortestDistance(graph); return 0; }

Output:

Time Complexity

The time complexity of the above-used algorithm is O(n^{2}). 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(n^{2}).

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.

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.

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 problems, interview experiences, and interview bundles for placement preparations.

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