//IMPLEMENTATION OF DIJKSTRA ALGORITHM
import java.io.*;
class Graph
{
BufferedReader Bobj= new BufferedReader(new InputStreamReader(System.in));
int g[][],v,e,d[],p[],visited[];
void Creategraph()throws IOException
{
int a,b,w;
System.out.print("ENTER THE NO OF VETEX=");
v=Integer.parseInt(Bobj.readLine());
System.out.print("ENTER THE NO OF EDGES=");
e=Integer.parseInt(Bobj.readLine());
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 EDGE INFORMATION\n");
System.out.print("ENTER THE SORCE VERTEX=");
a=Integer.parseInt(Bobj.readLine());
System.out.print("ENTER THE DESTINATION VERTEX=");
b=Integer.parseInt(Bobj.readLine());
System.out.print("ENTER THE WEIGTH OF EDGE =");
w=Integer.parseInt(Bobj.readLine());
g[a][b]=g[b][a]=w;
}
}
void CallDijktra()throws IOException
{
d=new int[v+1];
p=new int[v+1];
visited=new int[v+1];
for(int i=1;i<=v;i++)
{
p[i]=0;
visited[i]=0;
d[i]=32767;
}
Dijktra();
}
void Dijktra()throws IOException
{
BufferedReader Bobj= new BufferedReader(new InputStreamReader(System.in));
int dc,current,mincost=0,source,dest,c;
System.out.print("\n\n\n\n\n\n\nENTER THE SOURCE VERTEX=");
source=Integer.parseInt(Bobj.readLine());
System.out.print("ENTER THE DESTINATION VERTEX=");
dest=Integer.parseInt(Bobj.readLine());
current=source;
visited[current]=1;
d[current]=0;
dc=dest;
while (current!=dest)
{
for(int i=1;i<=v;i++)
{
if(g[current][i]!=0 && visited[i]!=1)
if (d[i]>g[current][i]+d[current])
{
d[i]=g[current][i]+d[current];
p[i]=current;
}
}
for(int i=1;i<=v;i++)
System.out.println("MINIMUM COST="+d[i]);System.out.println();
int min=32767;
for(int i=1;i<=v;i++)
{
if (visited[i]!=1 && d[i]
{
min=d[i];
current=i;
}
}
visited[current]=1;
}
System.out.println("******** GRAPH *********");
System.out.println("MINIMUM COST="+d[dest]);
}
}
class DijktraDemo
{
public static void main(String args[])throws IOException
{
Graph g=new Graph();
g.Creategraph();
g.CallDijktra();
}
}
/*Output:
ENTER THE NO OF VETEX=6
ENTER THE NO OF EDGES=10
ENTER THE EDGE INFORMATION
ENTER THE SORCE VERTEX=1
ENTER THE DESTINATION VERTEX=2
ENTER THE WEIGTH OF EDGE =3
ENTER THE EDGE INFORMATION
ENTER THE SORCE VERTEX=1
ENTER THE DESTINATION VERTEX=4
ENTER THE WEIGTH OF EDGE =2
ENTER THE EDGE INFORMATION
ENTER THE SORCE VERTEX=1
ENTER THE DESTINATION VERTEX=6
ENTER THE WEIGTH OF EDGE =20
ENTER THE EDGE INFORMATION
ENTER THE SORCE VERTEX=2
ENTER THE DESTINATION VERTEX=4
ENTER THE WEIGTH OF EDGE =8
ENTER THE EDGE INFORMATION
ENTER THE SORCE VERTEX=2
ENTER THE DESTINATION VERTEX=3
ENTER THE WEIGTH OF EDGE =7
ENTER THE EDGE INFORMATION
ENTER THE SORCE VERTEX=4
ENTER THE DESTINATION VERTEX=5
ENTER THE WEIGTH OF EDGE =3
ENTER THE EDGE INFORMATION
ENTER THE SORCE VERTEX=4
ENTER THE DESTINATION VERTEX=6
ENTER THE WEIGTH OF EDGE =22
ENTER THE EDGE INFORMATION
ENTER THE SORCE VERTEX=3
ENTER THE DESTINATION VERTEX=5
ENTER THE WEIGTH OF EDGE =6
ENTER THE EDGE INFORMATION
ENTER THE SORCE VERTEX=5
ENTER THE DESTINATION VERTEX=6
ENTER THE WEIGTH OF EDGE =4
ENTER THE EDGE INFORMATION
ENTER THE SORCE VERTEX=4
ENTER THE DESTINATION VERTEX=6
ENTER THE WEIGTH OF EDGE =22
ENTER THE SOURCE VERTEX=1
ENTER THE DESTINATION VERTEX=6
MINIMUM COST=0
MINIMUM COST=3
MINIMUM COST=32767
MINIMUM COST=2
MINIMUM COST=32767
MINIMUM COST=20
MINIMUM COST=0
MINIMUM COST=3
MINIMUM COST=32767
MINIMUM COST=2
MINIMUM COST=5
MINIMUM COST=20
MINIMUM COST=0
MINIMUM COST=3
MINIMUM COST=10
MINIMUM COST=2
MINIMUM COST=5
MINIMUM COST=20
MINIMUM COST=0
MINIMUM COST=3
MINIMUM COST=10
MINIMUM COST=2
MINIMUM COST=5
MINIMUM COST=9
******** GRAPH *********
MINIMUM COST=9
Process completed.
*/
Posts
ShareThis