//Program to Implement Multi Stage Graph
import java.io.*;
class multi {
public static void main(String args[]) throws IOException {
BufferedReader o = new BufferedReader(new InputStreamReader(System.in));
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
}
};
int i, j, c, a;
int s[] = new int[20];
int p[] = new int[20];
int temp[] = new int[20];
for (i = 0; i < 10; i++) {
s[i] = 0;
temp[i] = 0;
p[i] = 0;
}
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 (a) {
case 1:
for (i = 9; i >= 0; i--) {
c = 0;
for (j = 0; j <= 9; j++) {
if (x[i][j] != 0) {
if (c == 0) {
s[i] = s[j] + x[i][j];
p[i] = j;
c = 1;
} else {
temp[i] = s[j] + x[i][j];
if (temp[i] < s[i]) {
s[i] = s[j] + x[i][j];
p[i] = j;
}
}
}
}
}
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");
i = p[0];
System.out.print("0-->" + i);
while (i != 9) {
i = p[i];
System.out.print("-->" + i);
}
break;
case 2:
for (j = 0; j <= 9; j++) {
c = 0;
for (i = 0; i <= 9; i++) {
if (x[i][j] != 0) {
if (c == 0) {
s[j] = s[i] + x[i][j];
p[j] = i;
c = 1;
} else {
temp[j] = s[i] + x[i][j];
if (temp[j] < s[j]) {
s[j] = s[i] + x[i][j];
p[j] = i;
}
}
}
}
}
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");
i = p[9];
System.out.print("9-->" + i);
while (i != 0) {
i = p[i];
System.out.print("-->" + i);
}
break;
}
}
}
/*
Output For Multi Stage Graph
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-->0
*/