Thursday, April 14, 2011

Single Source Shortest Path


import java.io.*;
class Graph
{   DataInputStream d=new DataInputStream(System.in);
                int e,v,g[][];
                void creategraph()throws IOException
                {
                                int a,b,i,j;int source,dest;
                                System.out.println("enter no of vertices");
                                v=Integer.parseInt(d.readLine());
                                System.out.println("enter no of edges");
                                e=Integer.parseInt(d.readLine());
                                g=new int[v+1][v+1];
                                for(i=1;i<=v;i++)
                                for(j=1;j<=v;j++)
                                g[i][j]=0;
                               
                                for(i=1;i<=e;i++)
                                {
                                                int w;
                                                System.out.println("enter two vertices of edge "+i);
                                                a=Integer.parseInt(d.readLine());
                                                b=Integer.parseInt(d.readLine());
                                                System.out.println("enter weight of edge");
                                                w=Integer.parseInt(d.readLine());
                                                g[a][b]=g[b][a]=w;
                                }
                               
                                System.out.println("enter source ");
                                source=Integer.parseInt(d.readLine());
                                System.out.println("enter destination");
                                dest=Integer.parseInt(d.readLine());
                                callprim(source,dest);
                               
                }
               
                void callprim(int source,int dest)
                {
                int i;
                int p[]=new int[v+1];
                int d[]=new int[v+1];
                int visited[]=new int[v+1];
                for( i=1;i<=v;i++)
                {
                                d[i]=32000;
                                p[i]=visited[i]=0;
                }
                int current=source;
                visited[current]=1;
                d[current]=0;
                int c=0;
                while(c!=dest)
                {   int dc=d[current];
                                for(i=1;i<=v;i++)
                                if(g[current][i]!=0 && visited[i]!=1)
                                if(g[current][i]+dc < d[i])
                                {
                                                d[i]=g[current][i]+dc;
                                                p[i]=current;
                                }
                               
                                int min=32000;
                                for(i=1;i<=v;i++)
                                if(visited[i]!=1 && d[i]<min)
                                {
                                                min=d[i];
                                                current=i;
                                }
                                visited[current]=1;
                               
                                c++;
                }
               
                System.out.println("distance of "+dest+" from "+source+" is "+d[dest]);
}

}

public class Dij
{
                public static void main(String args[])throws IOException
                {
                                Graph g=new Graph();
                                g.creategraph();
                }
}

                       
Output:

enter no of vertices
4
enter no of edges
5
enter two vertices of edge 1
1
2
enter weight of edge
5
enter two vertices of edge 2
1
3
enter weight of edge
3
enter two vertices of edge 3
3
2
enter weight of edge
2
enter two vertices of edge 4
4
2
enter weight of edge
7
enter two vertices of edge 5
3
4
enter weight of edge
6
enter source
1
enter destination
4
distance of 4 from 1 is 9