Thursday, April 14, 2011

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