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.
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 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);
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; }
@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')
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);
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
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 of Multistage Graph
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() {
System.out.println("Distance from start: " + shortestDistance(graph)); } }
Python
N = 8 DIS = 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])
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.
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
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!
39+ registered 