Multi-Stage Graph

import java.util.*;

class Multistage{

    public int stages,stage_vertices[],c[][];

    public int cost[],p[],n;

    public Multistage(int max){

    c=new int [max][max];

    stage_vertices=new int[max];

    cost=new int[max];

    p=new int[max];

    }

   

    public int Get_min(int s,int n){

    int min=9999;

    int min_vertex=0;

    for(int i=0;i<n;i++){

    if(min>c[s][i]+cost[i]){

    min=c[s][i]+cost[i];

    min_vertex=i;

    }

    }

    return min_vertex;

    }

   

   

    public void Forward(int n){

    int i,r;

    int d[];

    d=new int[20];

    for (i=0;i<n;i++)

        cost[i]=0;

    for(i=n-2;i>=0;i--){

    r=Get_min(i,n);

    cost[i]=c[i][r]+cost[r];

    d[i]=r;

    }

    p[0]=0;

    p[stages-1]=n-1;

    for(i=1;i<stages-1;i++)

        p[i]=d[p[i-1]];

    }

   

    public void display(){

    int i;

    System.out.println("shortest path is\n");

    for(i=0;i<stages-1;i++)

        System.out.print("-"+(p[i]+1));

    System.out.println("-"+(p[i]+1));

    }

   

}//end class

public class MultistageGraph {

   

    public static void main(String []args){

    Scanner kbd=new Scanner(System.in);

    Multistage obj=new Multistage(20);

    int n=0;

    int i,j,m,p;

   

    System.out.print("\n Enter no of vertices\n");

    n=kbd.nextInt();

    System.out.println("\nEnter no of stages\n");

    obj.stages=kbd.nextInt();

    for(i=0;i<n;i++)

        for(j=0;j<n;j++)

            obj.c[i][j]=9999;

    for(i=0;i<obj.stages;i++){

    System.out.print("\n Enter no of vertices in stage "+(i+1)+" :");

    obj.stage_vertices[i]=kbd.nextInt();

    }

    i=0;

    j=obj.stage_vertices[0];

    for(m=0;m<obj.stages;m++){

    j=i+obj.stage_vertices[m];

    for(;i<j;i++)

        for(p=0;p<obj.stage_vertices[m+1];p++){

        System.out.print("\n Enter cost for "+(i+1)+" to "+(p+j+1)+" :");

        obj.c[i][p+j]=kbd.nextInt();

        }

    }

    obj.Forward(n);

    obj.display();

    }//end of main

}

/*

 * output:

Enter no of vertices 12

enter no of stages 5

 enter no of vertices in stage 1 :1

 enter no of vertices in stage 2 :4

 enter no of vertices in stage 3 :3

 enter no of vertices in stage 4 :3

 enter no of vertices in stage 5 :1

 enter cost for 1 to 2 :9

 enter cost for 1 to 3 :7

 enter cost for 1 to 4 :3

 enter cost for 1 to 5 :2

 enter cost for 2 to 6 :4

 enter cost for 2 to 7 :2

 enter cost for 2 to 8 :1

 enter cost for 3 to 6 :2

 enter cost for 3 to 7 :7

 enter cost for 3 to 8 :9999

 enter cost for 4 to 6 :9999

 enter cost for 4 to 7 :9999

 enter cost for 4 to 8 :11

 enter cost for 5 to 6 :9999

 enter cost for 5 to 7 :11

 enter cost for 5 to 8 :8

 enter cost for 6 to 9 :6

 enter cost for 6 to 10 :5

 enter cost for 6 to 11 :9999

 enter cost for 7 to 9 :4

 enter cost for 7 to 10 :3

 enter cost for 7 to 11 :9999

 enter cost for 8 to 9 :9999

 enter cost for 8 to 10 :5

 enter cost for 8 to 11 :6

 enter cost for 9 to 12 :4

 enter cost for 10 to 12 :2

 enter cost for 11 to 12 :5

 shortest path is

-1-2-7-10-12

*/