/*IMPLEMENTATION OF DIJKSTRA’S ALGORITHM*/

#include<stdio.h>

#include<limits.h>

#define maxnode 10

#define perm 1

#define tent 2

#define infinity INT_MAX

typedef struct nodelabel

{

   int predecessor;

   int length;

   int label;

}nodelabel;

int shortpath(a,n,s,t,path,dist)

int a[maxnode][maxnode],n,s,t,path[maxnode],*dist;

{

    nodelabel state[maxnode];

    int i,k,min,count,rpath[maxnode];

    *dist=0;

    for(i=1;i<=n;i++)

    {

             state[i].predecessor=0;

             state[i].length=infinity;

             state[i].label=tent;

    }

    state[s].predecessor=0;

    state[s].length=0;

    state[s].label=perm;

    k=s;

    do

    {

       for(i=1;i<=n;i++)

       {

              if(a[k][i]>0 && state[i].label==tent)

              {

                if(state[k].length+a[k][i]<state[i].length)

                {

                   state[i].predecessor=k;

                   state[i].length=state[k].length+a[k][i];

                }

              }

       }

       min=infinity;

       k=0;

       for(i=1;i<=n;i++)

       {

              if(state[i].label==tent&&state[i].length<min)

              {

                  min=state[i].length;

              k=i;

              }

       }

       if(k==0)

              return 0;

       state[k].label=perm;

    }while(k!=t);

    k=t;

    count=0;

    do

    {

       count++;

       rpath[count]=k;

       k=state[k].predecessor;

    }while(k!=0);

    for(i=1;i<=count;i++)

       path[i]=rpath[count-i+1];

    for(i=1;i<count;i++)

       *dist+=a[path[i]][path[i+1]];

    return count;

}

void main()

{

   int a[maxnode][maxnode],i,j;

   int path[maxnode];

   int from,to,dist,count,n;

   clrscr();

   printf("Enter no. of nodes:");

   scanf("%d",&n);

   for(i=1;i<=n;i++)

   {

       printf("Enter node %d",i);

       for(j=1;j<=n;j++)

              scanf("%d",&a[i][j]);

   }

   printf("\n From to");

   scanf("%d %d",&from,&to);

   count=shortpath(a,n,from,to,path,&dist);

   if(dist)

   {

      printf("\n Short path");

      printf("%d",path[1]);

      for(i=2;i<=count;i++)

             printf("-->%d",path[i]);

      printf("\nMinimum distance is %d \n",dist);

   }

   else

      printf("\n Path does not exists");

 

   getch();

}

 

OUTPUT

 

Enter no. of nodes:4

Enter node 1

0 3 4 0

Enter node 2

 0 0 6 20

Enter node 3

0 0  0 9

Enter node 4

15 0 0 0

 

 From to 2 4

 

 Short path2-->3-->4

Minimum distance is 15