Write
a program to find the shortest path between any two routers in a given subnet
using Dijkstra’s shortest path routing algorithm.
import java.util.*;
class Dijkstra
{
int
g[][];
int
v, e;
int
d[], p[], vis[];
void
CreateGraph()
{
int
a, b, w;
Scanner
is=new Scanner(System. in);
System.out.println("Enter
the Number of Nodes:");
v=is.nextInt();
System.out.println("Enter
the Number of Edges:");
e=is.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]=0;
for(int
i=1;i<=e;i++)
{
System.out.println("Enter
the Edges Info:");
a=is.nextInt();
b=is.nextInt();
System.out.println("Enter
the Weight of these Edges:");
w=is.nextInt();
g[a][b]=g[b][a]=w;
}
}
void
CallDij()
{
vis=new
int[v+1];
d=new
int[v+1];
p=new
int[v+1];
for(int
i=1;i<=v;i++)
p[i]=vis[i]=0;
for(int
i=1;i<=v;i++)
d[i]=32767;
Dij();
}
void
Dij()
{
int
c, cur, min, src, dest;
System.out.println("Enter
the Source and Destination Vertex:");
Scanner
is=new Scanner(System.in);
src=is.nextInt();
dest=is.nextInt();
cur=src;
vis[cur]=1;
d[cur]=0;
while(cur!=dest)
{
int
dc=d[cur];
for(int
i=1;i<=v;i++)
{
if(g[cur][i]!=0
&& vis[i]!=1)
if(g[cur][i]+dc<d[i])
{
d[i]=g[cur][i]+dc;
p[i]=cur;
}
}
min=32767;
for(int
i=1;i<=v;i++)
{
if(vis[i]!=1
&& d[i]<min)
{
min=d[i];
cur=i;
}
}
vis[cur]=1;
}
System.out.println("shortest
distance ="+d[dest]);
}
}
public class Exp2Dijkstra
{
public
static void main(String s[])
{
Dijkstra
g=new Dijkstra();
g.CreateGraph();
g.CallDij();
}
}
/*Output: -
Microsoft Windows XP [Version 5.1.2600]
(C) Copyright 1985-2001 Microsoft Corp.
C:\Documents and Settings\Sameer Kobal>cd\
C:\>set path="C:\Program
Files\Java\jdk1.6.0_17\bin"
C:\>javac Exp2Dijkstra.java
C:\>java Exp2Dijkstra
Enter the Number of Nodes:
5
Enter the Number of Edges:
5
Enter the Edges Info:
1 3
Enter the Weight of these Edges:
10
Enter the Edges Info:
3 5
Enter the Weight of these Edges:
20
Enter the Edges Info:
5 2
Enter the Weight of these Edges:
15
Enter the Edges Info:
2 4
Enter the Weight of these Edges:
9
Enter the Edges Info:
4 1
Enter the Weight of these Edges:
2
Enter the Source and Destination Vertex:
1 5
shortest distance =26
*/
