Dijikstra's Algorithm

SOURCE CODE:
#include<stdio.h>
int cost[20][20],visited[20],d[20],n;
void dijikstra(int source){
int i,j,min,u,v;
for(i=1;i<=n;i++){
visited[i]=0;
d[i]=cost[source][i];
}
visited[source]=0;d[source]=0;
for(j=2;j<=n;j++){
min=9999;//assuming is the max value
for(i=1;i<=n;i++){
if(!visited[i])
if(d[j]<min){
min=d[i];
u=i;
}
}
visited[u]=1;
for(v=1;v<=n;v++){
if(cost[u][v]!=9999 && visited[v]==0){
if(d[v]>cost[u][v]+d[u])
d[v]=cost[u][v]+d[u];
}
}
}
}
int main(){
int i,j,source;
printf("Enter # of vertices : \n");
scanf("%d",&n);
printf("Enter source vertex: \n");
scanf("%d",&source);//generally 1
printf("Enter the adjacency matrix :\n");
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
scanf("%d",&cost[i][j]);
if(cost[i][j]==0)
cost[i][j]=9999;
}
}
dijikstra(source);
printf("Shortest paths :\n");
for(i=1;i<=n;i++)
if(i!=source)
printf("%d --> %d  =  %d\n",source,i,d[i]);//if result is 9999 that means path dosen't exist
}

OUTPUT:
Enter # of vertices :
6
Enter source vertex:
1
Enter the adjacency matrix :
0 50 45 10 0 0
0 0 10 15 0 0
0 0 0 0 35 0
20 0 0 0 15 0
0 20 25 0 0 0
0 0 0 0 3 0

Shortest paths :
1 --> 2  =  45
1 --> 3  =  45
1 --> 4  =  10
1 --> 5  =  25
1 --> 6  =  9999

Comments