Implementation of Multi-Stage Graph in Java

//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
*/

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.