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
No comments:
Post a Comment