Search

0.4.4.2 Source Code

An implementation of Dijkstra's algorithm is given below.

#include 
 #include 
 
 #include "debug.h"
 
 #define NUM_NODES                          8
 #define NONE                               9999
 #define X(l)                               ((l) - 'A')
 #define Y(n)                               ((n) + 'A')
 
 struct _NODE
 {
   int iDist;
   int iPrev;
 };
 typedef struct _NODE NODE;
 
 struct _QITEM
 {
   int iNode;
   int iDist;
   int iPrev;
   struct _QITEM *qNext;
 };
 typedef struct _QITEM QITEM;
 
 QITEM *qHead = NULL;
 
 /*
                                        H
                                       / \
                                      1   2
                                     /     \
                                    F---4---G
                                   /         \
                                  4           2
                                 /             \
                                E---2---A---3---D
                                 \     / \     /
                                  3   1   2   3
                                   \ /     \ /
                                    B---2---C
 
 				   */
 
 
 
 
 
 int AdjMatrix[NUM_NODES][NUM_NODES] = 
 { 
         /*   A     B     C     D     E     F     G     H     */
   /* A */ { NONE,    1,    2,    3,    2, NONE, NONE, NONE },
   /* B */ {    1, NONE,    2, NONE,    3, NONE, NONE, NONE },
   /* C */ {    2,    2, NONE,    2, NONE, NONE, NONE, NONE },
   /* D */ {    3, NONE,    2, NONE, NONE, NONE,    2, NONE },
   /* E */ {    2,    3, NONE, NONE, NONE,    4, NONE, NONE },
   /* F */ { NONE, NONE, NONE, NONE,    4, NONE,    4,    1 },
   /* G */ { NONE, NONE, NONE,    2, NONE,    4, NONE,    2 },
   /* H */ { NONE, NONE, NONE, NONE, NONE,    1,    2, NONE }
 };
 
 int g_qCount = 0;
 
 
 void print_path (NODE *rgnNodes, int chNode)
 {
   if (rgnNodes[chNode].iPrev != NONE)
   {
     print_path(rgnNodes, rgnNodes[chNode].iPrev);
   }
   printf (" %c", Y(chNode));
   fflush(stdout);
 }
 
 
 void enqueue (int iNode, int iDist, int iPrev)
 {
   QITEM *qNew = (QITEM *) malloc(sizeof(QITEM));
   QITEM *qLast = qHead;
 
   if (!qNew) 
   {
     fprintf(stderr, "Out of memory.\n");
     exit(1);
   }
   qNew->iNode = iNode;
   qNew->iDist = iDist;
   qNew->iPrev = iPrev;
   qNew->qNext = NULL;
 
   if (!qLast) 
   {
     qHead = qNew;
   }
   else
   {
     while (qLast->qNext) qLast = qLast->qNext;
     qLast->qNext = qNew;
   }
   g_qCount++;
   ASSERT(g_qCount);
 }
 
 
 void dequeue (int *piNode, int *piDist, int *piPrev)
 {
   QITEM *qKill = qHead;
 
   if (qHead)
   {
     ASSERT(g_qCount);
     *piNode = qHead->iNode;
     *piDist = qHead->iDist;
     *piPrev = qHead->iPrev;
     qHead = qHead->qNext;
     free(qKill);
     g_qCount--;
   }
 }
 
 
 int qcount (void)
 {
   return(g_qCount);
 }
 
 
 int main(void) 
 {
 
   NODE rgnNodes[NUM_NODES];
   char rgchLine[255];
   char chStart, chEnd, ch;
   int iPrev, iNode;
   int i, iCost, iDist;
 
   for (ch = 'A'; ch <= 'A' + NUM_NODES; ch++)
   {
     rgnNodes[X(ch)].iDist = NONE;
     rgnNodes[X(ch)].iPrev = NONE;
   }
 
   printf("What is the starting node? ");
   gets(rgchLine);
   chStart = toupper(rgchLine[0]);
 
   printf("What is the ending node? ");
   gets(rgchLine);
   chEnd = toupper(rgchLine[0]);
 
   if (chStart == chEnd) 
   {
     printf("Shortest path is 0 in cost.\nJust stay where you are.\n");
     exit(0);
   }
   else
   {
     chStart = X(chStart);
     chEnd = X(chEnd);
     rgnNodes[chStart].iDist = 0;
     rgnNodes[chStart].iPrev = NONE;
 
     enqueue (chStart, 0, NONE);
 
     while (qcount() > 0)
     {
       dequeue (&iNode, &iDist, &iPrev);
       for (i = 0; i < NUM_NODES; i++)
       {
         if ((iCost = AdjMatrix[iNode][i]) != NONE)
 	{
 	  if ((NONE == rgnNodes[i].iDist) || 
 	      (rgnNodes[i].iDist > (iCost + iDist)))
 	  {
 	    rgnNodes[i].iDist = iDist + iCost;
             rgnNodes[i].iPrev = iNode;
 	    enqueue (i, iDist + iCost, iNode);
           }
 	}
       }
     }
 
     printf("Shortest path is %d in cost.\n", rgnNodes[chEnd].iDist);
     printf("Path is: ");
     print_path(rgnNodes, chEnd);
   }
  
 
   exit(0);
 }