PROGRAM TO FIND THE SHORTEST PATH USING DIJKSTRAS SHORTEST PATH ALGORITHM

import java.io.*;
import java.util.*;


class Graph
{
int MAXNODES=50;
int MAX1=150;
int INFINITY=5000;
int i,j,finall=0;
int smalldist,newdist,k,s,d,current,n,distcurr;
int weight[][]=new int[MAXNODES][MAXNODES];
int distance[]=new int[MAXNODES];
int visit[]=new int[MAXNODES];
int precede[]=new int[MAXNODES];
int path[]=new int[MAX1];




/*function to print the result*/
void Display_Result()
{
i=d;
path[finall]=d;
finall++;
while(precede[i] != s)
{
j = precede[i];
i = j;
path[finall] = i;
finall++;
}
path[finall] = s;
System.out.println("\nThe shortest path followed is : \n\n");
for(i=finall;i>0;i--)
System.out.print("\t\t( "+ path[i]+" ->"+path[i-1]+" ) with cost = ");
System.out.print(weight[path[i]][path[i-1]]+"\n\n");
System.out.println("For the Total Cost = "+distance[d]);
}/*end Display_Result*/


/*function to read number*/
int getNumber()
{
String str;
int ne=0;
InputStreamReader input=new InputStreamReader(System.in);
BufferedReader in=new BufferedReader(input);
try
{
str=in.readLine();
ne=Integer.parseInt(str);
}
catch(Exception e)
{
System.out.println("I/O Error");
}
return ne;
}/*end getNumber*/


/*function for shortest path*/
void SPA()
{
System.out.print("\nEnter the number of nodes (Less than 50) in the matrix : ");
n=getNumber();


System.out.print("\nEnter the cost matrix : \n\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
System.out.print("\nCost "+(i+1)+"--"+(j+1)+" : ");
weight[i][j]=getNumber();
}




System.out.print("\nEnter the source node : ");
s=getNumber();


System.out.print("\nEnter the destination node : ");
d=getNumber();


for (i=0;i<n;i++)
{
distance[i]=INFINITY;
precede[i]=INFINITY;
}
distance[s]=0;
current=s;
visit[current]=1;
while(current!=d)
{
distcurr=distance[current];
smalldist=INFINITY;
for(i=0; i<n; i++)
{
if(visit[i]==0)
{
newdist=distcurr+weight[current][i];
if(newdist<distance[i])
{
distance[i]=newdist;
precede[i]=current;
}
if(distance[i]< smalldist)
{
smalldist=distance[i];
k=i;
}
}
}
current = k;
visit[current]=1;
}
Display_Result();
}


}/*end SPA*/




class Dijkstra
{
public static void main(String args[])
{
Graph g=new Graph();
g.SPA();
}
}






/*


Enter the number of nodes (Less than 50) in the matrix : 6


Enter the cost matrix :




Cost 1--1 : 5000


Cost 1--2 : 6


Cost 1--3 : 3


Cost 1--4 : 5000


Cost 1--5 : 5000


Cost 1--6 : 5000


Cost 2--1 : 6


Cost 2--2 : 5000


Cost 2--3 : 2


Cost 2--4 : 5


Cost 2--5 : 5000


Cost 2--6 : 5000


Cost 3--1 : 3


Cost 3--2 : 2


Cost 3--3 : 5000


Cost 3--4 : 3


Cost 3--5 : 4


Cost 3--6 : 5000


Cost 4--1 : 5000


Cost 4--2 : 5


Cost 4--3 : 3


Cost 4--4 : 5000


Cost 4--5 : 2


Cost 4--6 : 3


Cost 5--1 : 5000


Cost 5--2 : 5000


Cost 5--3 : 4


Cost 5--4 : 2


Cost 5--5 : 5000


Cost 5--6 : 5


Cost 6--1 : 5000


Cost 6--2 : 5000


Cost 6--3 : 5000


Cost 6--4 : 3


Cost 6--5 : 5


Cost 6--6 : 5000


Enter the source node : 0


Enter the destination node : 5


The shortest path followed is :




                ( 0 ->2 ) with cost = 3




                ( 2 ->3 ) with cost = 3




                ( 3 ->5 ) with cost = 3




For the Total Cost = 9
*/