MultiStage Graph
Explanation Video
Useful for representing resource allocation problem.
Time Complexity = O(n^2)
Java program
/* package codechef; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* MultiStageGraph to find rout of shortest path. This program can be
used to print shortest rout or sum of shortest path. */
class MultiStageGraph {
// Find shortest path
private static String findShortestPath() {
// Get input graph
int[][] graph = populateGraph();
// Size of the graph
int size = graph.length;
// Store the result
StringBuilder result = new StringBuilder("1");
// Store cost of choosing particular rout
int[] cost = new int[size];
// Store distance
int[] distance = new int[size];
// Store rout path
int[] path = new int[size];
// Assuming the cost to reach last node from the same node is 0;
cost[size - 1] = 0;
for(int i = size - 2; i >= 1; i--) {
int min = Integer.MAX_VALUE;
for(int j = i + 1; j < size; j++) {
if(graph[i][j] != 0 && (graph[i][j] + cost[j]) < min) {
min = graph[i][j] + cost[j];
distance[i] = j;
}
}
cost[i] = min;
}
// Print cost
System.out.print("Print Cost : ");
for(int i = 1; i < size; i++) {
System.out.print(cost[i] + " ");
}
System.out.println(); // Line break
// Print distance
System.out.print("Print distance : ");
for(int i = 1; i < size; i++) {
System.out.print(distance[i] + " ");
}
System.out.println(); // Line break
// Initialize first node to traverse as 1
path[1] = 1;
for(int index = 2; index < size; index++) {
path[index] = distance[path[index - 1]];
result.append("-->");
result.append(path[index]);
if(path[index] == size - 1) {
break; // break as already found rout from source to destination
}
}
return result.toString();
}
// Populate graph. Values can be inserted from any source ie. keyboard
private static int[][] populateGraph() {
int[][] graph = {
{0,0,0,0,0,0,0,0,0},
{0,0,2,1,3,0,0,0,0},
{0,0,0,0,0,2,3,0,0},
{0,0,0,0,0,6,7,0,0},
{0,0,0,0,0,6,8,9,0},
{0,0,0,0,0,0,0,0,6},
{0,0,0,0,0,0,0,0,4},
{0,0,0,0,0,0,0,0,5},
{0,0,0,0,0,0,0,0,0}
};
return graph;
}
public static void main (String[] args) throws java.lang.Exception {
System.out.println("shortest path : " + findShortestPath());
}
}
Comments
Post a Comment