Thursday, April 14, 2011

All Pair Shortest Path


import java.io.*;
import java.util.*;
class graph
{
        int g[][],v,e,i,j,k;
        void creatgraph()
        {
                        Scanner s=new Scanner(System.in);
                        int a,b,w;
                        System.out.println("Enter no of vertices");
                        v=s.nextInt();
                        System.out.println("Enter no of edges");
                        e=s.nextInt();
                        g=new int[v+1][v+1];
                        for(int i=1;i<=v;i++)
                        for(int j=1;j<=v;j++)
        g[i][j]=32767;
        for(int i=1;i<=v;i++)
        g[i][i]=0;
                        for(int i=1;i<=e;i++)
                        {
                                        System.out.println("Enter edge information:");
                                        a=s.nextInt();
                                        b=s.nextInt();
                                        System.out.println("Enter weight of edge:");
                                        w=s.nextInt();
                                        g[a][b]=w;
                        }
        }
    void allpair()
    {
        for(int k=1;k<=v;k++)
        for(int i=0;i<=v;i++)
        for(int j=0;j<=v;j++)
        g[i][j]=Math.min(g[i][j],g[i][k]+g[k][j]);
        System.out.println("");
        System.out.println("The shortest path for all vertices is given by a matrix");
        System.out.println("");
        for(int i=1;i<=v;i++)
        {
            for(int j=1;j<=v;j++)
            {
            System.out.print(g[i][j]+"    ");
            }
            System.out.println();
        }
    }
}
class allpairshortest
{
        public static void main(String args[])
        {
                        graph g=new graph();
                        g.creatgraph();
                        g.allpair();
        }
}

OUTPUT:


Enter no of vertices
4
Enter no of edges
5
Enter edge information:
1
2
Enter weight of edge:
7
Enter edge information:
2
3
Enter weight of edge:
8
Enter edge information:
3
4
Enter weight of edge:
9
Enter edge information:
4
1
Enter weight of edge:
10
Enter edge information:
1
3
Enter weight of edge:
11

The shortest path for all vertices is given by a matrix




 0    7   11   20
27    0    8   17
19   26    0    9
10   17   21    0
Press any key to continue...