Dijkstra's Algorithm Method 1

C Program For Dijkstra's Algorithm(Greedy Algorithm) Method 1

Source Code:


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

int minimum_dist_vertex(int dist[],char status[],int N);

main()
{
   int L[100][100],dist[100],prev[100];
   char status[100];
   int Source,Dest,i,j,k,N,Vstar;

   printf("Enter Number Of Vertices:");
   scanf("%d",&N);

   printf("\nEnter Length Matrix:\n\n");
   for(i=1;i<=N;i++)
      for(j=1;j<=N;j++)
	 scanf("%d", &L[i][j]);

   printf("\nEnter Source Node: ");
   scanf("%d",&Source);

   printf("\nEnter Destination Node: ");
   scanf("%d",&Dest);

   status[Source]='!';
   dist[Source]=0;
   prev[Source]=0;

   for(i=1;i<=N;i++)
      if(i!=Source)
      {
	 status[i]='?';
	 dist[i]=L[Source][i];
	 prev[i]=Source;
      }
   k=1;
   do
   {
   printf("\nVertex\t\t");
   for(i=1;i<=N;i++)
      printf("V[%d]\t",i);
   printf("\n");
   printf("Status\t\t");
   for(i=1;i<=N;i++)
      printf("%c\t",status[i]);
   printf("\n");
   printf("Dist  \t\t");
   for(i=1;i<=N;i++)
      printf("%d\t",dist[i]);
   printf("\n");
   printf("Prev  \t\t");
   for(i=1;i<=N;i++)
      printf("%d\t",prev[i]);
   printf("\n");
   for(i=1;i<=70;i++)
   printf("_");

   Vstar=minimum_dist_vertex(dist,status,N);
   status[Vstar]='!';

   for(i=1;i<=N;i++)
   {
      if(status[i]=='?')
      {
	 if (dist[i]> dist[Vstar]+L[Vstar][i])
	 {
	     dist[i]=dist[Vstar]+L[Vstar][i];
	     prev[i]=Vstar;
	 }
      }
   }
   k++;
}
while(k<=N);
printf("\n\nThe Minimum Distance Is:  %d",dist[Dest]);
getch();
}
int minimum_dist_vertex(int dist[],char status[],int N)
{
   int minimum,minposition,i;
   minimum=INFINITY;
   minposition=1;
   for(i=1;i<=N;i++)
     if(status[i]=='?')
       if(dist[i]<minimum)
       {
	  minimum=dist[i];
	  minposition=i;
	}
   return(minposition);
}