Java the program find shortest paths to other vertices using Dijkstra’s algorithm for weighted connected graph

				
					import java.util.Scanner;
public class Dijkstra {
/**
* @param args
*/
int d[]=new int[10];
int p[]=new int[10];
int visited[]=new int[10];
public void dijk(int[][]a, int s, int n)
{
int u=-1,v,i,j,min;
for(v=0;v
{
d[v]=99;
p[v]=-1;
} d[s]=0;
for(i=0;i
min=99;
for(j=0;j
if(d[j]
{
min=d[j];
u=j;
}}
visited[u]=1;
for(v=0;v
if((d[u]+a[u][v]
{
d[v]=d[u]+a[u][v];
p[v]=u;
}
}
}
}
void path(int v,int s)
{
if(p[v]!=-1)
path(p[v],s);
if(v!=s)
System.out.print("->"+v+" ");
}
void display(int s,int n){
int i;
for(i=0;i
{
if(i!=s){
System.out.print(s+" ");
path(i,s);

}
if(i!=s)
System.out.print("="+d[i]+" ");
System.out.println();
}
}
public static void main(String[] args) {
int a[][]=new int[10][10];
int i,j,n,s;
System.out.println("enter the number of vertices");
Scanner sc = new Scanner(System.in);
n=sc.nextInt();
System.out.println("enter the weighted matrix");
for(i=0;i
for(j=0;j
a[i][j]=sc.nextInt();
System.out.println("enter the source vertex");
s=sc.nextInt();
Dijkstra tr=new Dijkstra();
tr.dijk(a,s,n);
System.out.println("the shortest path between source"+s+"to remaining
vertices are");
tr.display(s,n);
sc.close();
}
}
				
			
Output:
enter the number of vertices
5
enter the weighted matrix
0   3   99   7   99
3    0  4     2  99
99 4   0     5  6
5    2   5     0  4
99 99 6     4  0
enter the source vertex
0
the shortest path between source to remaining vertices are
0 ->1 =3
0 ->1 ->2 =7
0 ->1 ->3 =5
0 ->1 ->3 ->4 =9

Leave a Reply