C program for Shortest path using Dijkstra's Algorithm

#define INFINITY 9999
#include <stdio.h>
#include <conio.h>
#define MAX 10

void dijikstra(int G[MAX][MAX],int n, int startnode);
void main()
{ int G[MAX][MAX],i,j,n,u;
  clrscr();
  printf("\nEnter no. of vertices : ");
  scanf("%d",&n);
  printf("\nEnter adjacency matrix : ");
  for(i=0;i<n;i++)
   for(j=0;j<n;j++)
    scanf("%d",&G[i][j]);
  printf("\nEnter the starting node : ");
  scanf("%d",&u);
  dijikstra(G,n,u);
  getch();
}

void dijikstra(int G[MAX][MAX],int n, int startnode)
{ int cost[MAX][MAX],distance[MAX],pred[MAX];
  int visited[MAX],count,mindistance,nextnode,i,j;
  /*pred[] stores the predecessor of each node
  count gives the number of nodes seen so far*/

  //create the cost matrix
  for(i=0;i<n;i++)
    for(j=0;j<n;j++)
     if(G[i][j]==0)
       cost[i][j]=INFINITY;
     else
       cost[i][j]=G[i][j];
  //initialize
  for(i=0;i<n;i++)
   { distance[i]=cost[startnode][i];
     pred[i]=startnode;visited[i]=0;
   }
  distance[startnode]=0;visited[startnode]=1;
  count=1;
  while(count<n-1)
   { mindistance=INFINITY ;
// nextnode is the node at minimum distance
     for(i=0;i<n;i++)
       if(distance[i] < mindistance && !visited[i])
{ mindistance=distance[i];
  nextnode=i;
}
//check if a better path exist through nextnode
   visited[nextnode]=1;
   for(i=0;i<n;i++)
    if(!visited[i])
      if(mindistance+cost[nextnode][i]<distance[i])
{ distance[i]=mindistance+cost[nextnode][i];
  pred[i]=nextnode;
}
   count++;
 }

 //print the path and distance of each node
 for(i=0;i<n;i++)
    if(i!=startnode)
      { printf("\n Distance of %d = %d ",i,distance[i]);
printf("\nPath = %d ",i);
j=i;
do {
    j=pred[j];
    printf("<- %d ",j);
  }while(j!=startnode);
     }
}


OUTPUT:-



Enter no. of vertices : 4

Enter adjacency matrix :
0 1 1 1
1 0 1 0
1 1 0 1
1 0 1 0

Enter the starting node : 1

 Distance of 0 = 1
Path = 0 <- 1
 Distance of 2 = 1
Path = 2 <- 1
 Distance of 3 = 2
Path = 3 <- 0 <- 1