Dijkstra's Algorithm/Sample 2.cpp

//
// Dijkstra's Algorithm sample stolen 2002 by Louis. (Minor revision 2021.)
//
#include "iostream.h"
#include "Windows.h"
#include "stdio.h"
#include "assert.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, NONE, NONE, NONE, NONE,    1, NONE },
    /* B */ {    1, NONE,    1, NONE, NONE, NONE, NONE,    1 },
    /* C */ { NONE,    1, NONE,    1, NONE, NONE, NONE, NONE },
    /* D */ { NONE, NONE,    1, NONE,    1, NONE, NONE, NONE },
    /* E */ { NONE, NONE, NONE,    1, NONE,    1, NONE, NONE },
    /* F */ { NONE, NONE, NONE, NONE,    1, NONE,    1, NONE },
    /* G */ {    1, NONE, NONE, NONE, NONE,    1, NONE,    1 },
    /* H */ { NONE,    1, NONE, NONE, NONE, NONE,    1, NONE }
};

/*
16777216        1               16777216        16777216        16777216        16777216        1               16777216
1               16777216        1               16777216        16777216        16777216        16777216        1
16777216        1               16777216        1               16777216        16777216        16777216        16777216
16777216        16777216        1               16777216        1               16777216        16777216        16777216
16777216        16777216        16777216        1               16777216        1               16777216        16777216
16777216        16777216        16777216        16777216        1               16777216        1               16777216
1               16777216        16777216        16777216        16777216        1               16777216        1
16777216        1               16777216        16777216        16777216        16777216        1               16777216
*/

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++)
            {
                (iCost = AdjMatrix[iNode][i]);
                if (iCost != 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);
        char a[255];
        gets (a);
    }

    exit(0);
}


[END OF FILE]