In this post, we’ll explore how to implement a Multi-Stage Graph in Java. If you’ve ever dealt with finding the shortest path where you have to move through specific phases or “stages” one by one, you’ve encountered this exact problem.
What exactly is a Multi-Stage Graph?
Imagine a directed, weighted graph where all nodes are neatly organized into distinct stages. You’re only allowed to move forward—meaning a node in stage 1 can only connect to a node in stage 2, enforcing a strict stage ordering. The ultimate goal here is to find the absolute cheapest path from your starting point (the source) all the way to your final target (the destination).
If this sounds like a perfect job for Dynamic Programming, you’re absolutely right. Instead of brute-forcing every possible route, we build the overall shortest path by cleverly stitching together the optimal sub-paths between each stage.
In this walkthrough, we’ll focus on two different ways to compute that path:
- Forward Method: Start at the finish line and work your way backward to compute the costs.
- Backward Method: Start at the source and push forward until you hit the destination.
How the Algorithm Actually Works
Since we’re leaning on Dynamic Programming, our first step is breaking the big problem into smaller, manageable subproblems. Let’s say Cost(i, j) represents the minimum cost to get from node j (which lives in stage i) all the way to our destination. The core logic boils down to this simple recurrence relation:
Cost(i, j) = min { weight(j, k) + Cost(i+1, k) }
In plain English? To find the cheapest path from node j, we look at all the nodes k in the next stage that j can reach. We take the cost of jumping to k, add it to the known cheapest path from k to the finish line, and pick the smallest total.
Here’s how we build it out in the code:
- Graph Representation:
We use a straightforward 2D matrix wherex[i][j]holds the weight of the edge between nodeiand nodej. Keep in mind that a value of0specifically means there’s no direct edge there (assuming all your valid edge weights are strictly positive). - Crunching the Costs:
- In the Forward Method, we start from the destination node and move backward stage by stage, figuring out the minimum cost to reach the destination from each preceding node.
- In the Backward Method, we start from the source node and compute the minimum cost to reach every subsequent node until we finally hit the destination.
- Tracing the Optimal Path:
As we calculate costs, we leave a breadcrumb trail by explicitly tracking the parent (or “next”) node. Once the math is done, we simply follow the crumbs to print out the final optimal path. - A Few Gotchas (Assumptions & Limitations):
For the sake of this tutorial, our implementation assumes nodes are sequentially numbered. Also, if a node is completely stranded (unreachable), its cost might remain zero or uninitialized. If you’re adapting this for production where a weight of0is actually valid, you’ll definitely want to handle that edge case. Finally, we don’t explicitly store the stages; the stage ordering is implicitly handled by how we number and loop through the nodes.
Performance Check:
Time Complexity: O(|V| + |E|) — since we evaluate each edge exactly once, it’s highly efficient.
Space Complexity: O(|V|) — to store our cost array and path breadcrumbs (not counting the adjacency matrix itself).
Java Code Implementation
import java.io.*;
class multi {
public static void main(String args[]) throws IOException {
// Reading input from the user
BufferedReader o = new BufferedReader(new InputStreamReader(System.in));
// Defining the multi-stage graph as a 2D array where x[i][j] denotes the cost from node i to node j
int x[][] = {
{0, 1, 2, 3, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 4, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 4, 3, 0, 0, 0, 0},
{0, 0, 0, 0, 2, 1, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 6, 7, 2, 0},
{0, 0, 0, 0, 0, 0, 4, 2, 3, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 2},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 3},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
};
// Arrays to store the minimum cost and the parent for each node
int i, j, c, a;
int s[] = new int[20]; // Array to store the minimum cost to reach each stage
int p[] = new int[20]; // Array to store the parent of each node
int temp[] = new int[20]; // Temporary array for cost calculations
// Initializing the arrays for cost and parent nodes
for (i = 0; i < 10; i++) {
s[i] = 0;
temp[i] = 0;
p[i] = 0;
}
// Displaying the menu to the user to choose between the Forward or Backward method
System.out.println("\n\nProgram for MultiStage Graph\n\n");
System.out.println("Select Any one Method\n");
System.out.println("1. Forward Method\n");
System.out.println("2. Backward Method\n\t");
a = Integer.parseInt(o.readLine());
// Switch statement to select between Forward or Backward Method
switch (a) {
case 1:
// Forward Method: Start from the destination node and compute the cost for each stage
for (i = 9; i >= 0; i--) {
c = 0;
// Check all possible connections for the current node
for (j = 0; j <= 9; j++) {
if (x[i][j] != 0) { // If there is a connection from node i to node j
if (c == 0) { // First connection for node i
s[i] = s[j] + x[i][j]; // Compute the cost
p[i] = j; // Store the parent node
c = 1;
} else {
temp[i] = s[j] + x[i][j]; // Calculate the cost for the new connection
if (temp[i] < s[i]) { // Update the cost and parent if the new cost is less
s[i] = s[j] + x[i][j];
p[i] = j;
}
}
}
}
}
// Displaying the Source-Cost-Parent table
System.out.println("\nSource Cost Parent");
for (i = 9; i >= 0; i--) {
System.out.print("\n " + i);
System.out.print(" \t " + s[i]);
System.out.print(" \t " + p[i]);
}
System.out.println("\n\n");
System.out.println("\n\nOptimal Path:\n\t");
// Tracing the optimal path from source (0) to destination (9)
i = p[0];
System.out.print("0-->" + i);
while (i != 9) { // Keep tracing the parent nodes until we reach the destination
i = p[i];
System.out.print("-->" + i);
}
break;
case 2:
// Backward Method: Start from the source node and compute the cost to each destination node
for (j = 0; j <= 9; j++) {
c = 0;
// Check all possible connections for the current node
for (i = 0; i <= 9; i++) {
if (x[i][j] != 0) { // If there is a connection from node i to node j
if (c == 0) { // First connection for node j
s[j] = s[i] + x[i][j]; // Compute the cost
p[j] = i; // Store the parent node
c = 1;
} else {
temp[j] = s[i] + x[i][j]; // Calculate the cost for the new connection
if (temp[j] < s[j]) { // Update the cost and parent if the new cost is less
s[j] = s[i] + x[i][j];
p[j] = i;
}
}
}
}
}
// Displaying the Source-Cost-Parent table
System.out.println("\nSource Cost Parent");
for (i = 0; i <= 9; i++) {
System.out.print("\n " + i);
System.out.print(" \t " + s[i]);
System.out.print(" \t " + p[i]);
}
System.out.println("\n\n");
System.out.println("\n\nOptimal Path:\n\t");
// Tracing the optimal path from source (0) to destination (9)
i = p[9];
System.out.print("9-->" + i);
while (i != 0) { // Keep tracing the parent nodes until we reach the source
i = p[i];
System.out.print("-->" + i);
}
break;
}
}
}Sample Output
Program for MultiStage Graph
Select Any one Method
1. Forward Method
2. Backward Method
1
Source Cost Parent
9 0 0
8 3 9
7 2 9
6 1 9
5 4 7
4 5 8
3 5 5
2 7 5
1 9 4
0 8 3
Optimal Path:
0-->3-->5-->7-->9
Program for MultiStage Graph
Select Any one Method
1. Forward Method
2. Backward Method
2
Source Cost Parent
0 0 0
1 1 0
2 2 0
3 3 0
4 5 1
5 4 3
6 8 5
7 6 5
8 7 4
9 8 7
Optimal Path:
9-->7-->5-->3-->0Explanation of the Output
Let’s break down the output step by step in more detail, both for the Forward Method and the Backward Method.
1. Forward Method
Step 1: Source-Cost-Parent Table
After selecting the Forward Method, the program starts from the destination node (node 9) and works backwards to compute the minimum cost and the parent node for each stage. The output shows the Source-Cost-Parent table, which represents the minimum cost to reach each node and its parent node in the optimal path.
Here’s the table for the Forward Method:
Source Cost Parent
9 0 0
8 3 9
7 2 9
6 1 9
5 4 7
4 5 8
3 5 5
2 7 5
1 9 4
0 8 3- Source (Node): The node number.
- Cost: The minimum cost to reach that node from the destination (node 9) in the case of the Forward Method.
- Parent: The parent node that leads to the optimal path for that particular node.
Step 2: How the Costs Are Computed
To understand how the costs are calculated, let’s take a look at how the program computes the minimum cost for each node. The algorithm starts at node 9 (destination) and calculates the cost for each node moving backward through the stages:
- For node 9:
- The minimum cost is
0because we are at the destination. - There is no parent because this is the end node.
- The minimum cost is
- For node 8:
- The possible connection is from node 9 to node 8 with a cost of 3 (
x[9][8] = 3). - The total cost is 3 (the cost from node 9 to node 8).
- The parent is node 9, as it’s the only node that connects to node 8.
- The possible connection is from node 9 to node 8 with a cost of 3 (
- For node 7:
- The possible connection is from node 9 to node 7 with a cost of 2 (
x[9][7] = 2). - The total cost is 2 (the cost from node 9 to node 7).
- The parent is node 9.
- The possible connection is from node 9 to node 7 with a cost of 2 (
- This pattern continues for all the other nodes, with the minimum cost calculated for each based on available connections.
Step 3: Tracing the Optimal Path
After calculating the cost and parent nodes, the algorithm then traces the optimal path from the source (node 0) to the destination (node 9).
Here’s how the path is traced:
- Start from node 0, and look at the parent of node 0, which is node 3 (from the table).
- Move to node 3, and the parent of node 3 is node 5.
- Move to node 5, and the parent of node 5 is node 7.
- Move to node 7, and the parent of node 7 is node 9.
- The destination node 9 has no parent (it’s the end of the path).
Thus, the optimal path for the Forward Method is:
Optimal Path:
0-->3-->5-->7-->92. Backward Method
Step 1: Source-Cost-Parent Table
After selecting the Backward Method, the program starts from the source node (node 0) and works forwards to compute the minimum cost and parent node for each stage. The output shows the Source-Cost-Parent table, representing the minimum cost to reach each node and its parent node in the optimal path.
Here’s the table for the Backward Method:
Source Cost Parent
0 0 0
1 1 0
2 2 0
3 3 0
4 5 1
5 4 3
6 8 5
7 6 5
8 7 4
9 8 7- Source (Node): The node number.
- Cost: The minimum cost to reach that node from the source (node 0) in the case of the Backward Method.
- Parent: The parent node that leads to the optimal path for that particular node.
Step 2: How the Costs Are Computed
In the Backward Method, the algorithm starts at node 0 (source) and calculates the cost for each node moving forward to the destination (node 9). The cost is calculated in a similar way as in the Forward Method, but this time we compute the cost from the source to the destination.
- For node 0:
- The cost is 0 because it’s the source node.
- There is no parent because this is the starting node.
- For node 1:
- The possible connection is from node 0 to node 1 with a cost of 1 (
x[0][1] = 1). - The total cost is 1.
- The parent is node 0.
- The possible connection is from node 0 to node 1 with a cost of 1 (
- For node 2:
- The possible connection is from node 0 to node 2 with a cost of 2 (
x[0][2] = 2). - The total cost is 2.
- The parent is node 0.
- The possible connection is from node 0 to node 2 with a cost of 2 (
- This pattern continues for all the other nodes.
Step 3: Tracing the Optimal Path
After calculating the cost and parent nodes, the algorithm then traces the optimal path from the source (node 0) to the destination (node 9).
Here’s how the path is traced:
- Start from node 9, and look at the parent of node 9, which is node 7 (from the table).
- Move to node 7, and the parent of node 7 is node 5.
- Move to node 5, and the parent of node 5 is node 3.
- Move to node 3, and the parent of node 3 is node 0.
- The source node 0 has no parent (it’s the start of the path).
Thus, the optimal path for the Backward Method is:
Optimal Path:
9-->7-->5-->3-->0