Search
Next: 0.4.5 Spanning Trees Up: 0.4.4 Dijkstra's Algorithm - Previous: 0.4.4.1 Analysis

### 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;

/*
H
/ \
1   2
/     \
F---4---G
/         \
4           2
/             \
E---2---A---3---D
\     / \     /
3   1   2   3
\ /     \ /
B---2---C

*/

{
/*   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));

if (!qNew)
{
fprintf(stderr, "Out of memory.\n");
exit(1);
}
qNew->iNode = iNode;
qNew->iDist = iDist;
qNew->iPrev = iPrev;
qNew->qNext = NULL;

if (!qLast)
{
}
else
{
while (qLast->qNext) qLast = qLast->qNext;
qLast->qNext = qNew;
}
g_qCount++;
ASSERT(g_qCount);
}

void dequeue (int *piNode, int *piDist, int *piPrev)
{

{
ASSERT(g_qCount);
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);
}

```

Scott Gasch
1999-07-09