C言語で書いてみました

■ ダイクストラのアルゴリズム（平成18年春午後1問5）

/*
 *  ソフトウェア開発 平成18年春午後1問5
 *  グラフの最短経路
 *  （ダイクストラのアルゴリズム）
 */

#include <stdio.h>

#define N_NODE      5
#define MAX_VALUE   100
#define VISITED     1
#define UNVISITED   0

int distance[N_NODE], status[N_NODE], w[N_NODE][N_NODE];
int start = 0; /* A */
int datasize = N_NODE;
int previous[N_NODE], route[N_NODE], top = -1;

void print_status(int m)
{
    int i;
    if (m == -1) printf("  ");
    else printf("%c ", 'A' + m);
    for (i = 0; i < datasize; i++) {
        if (distance[i] == MAX_VALUE)
            printf(" M ");
        else
            printf("%2d ", distance[i]);
    }
    putchar('\n');
}

void push(int x)
{
    if (top < N_NODE - 1) {
        top = top + 1;
        route[top] = x;
    }
}

int pop()
{
    if (top >= 0) {
        top = top - 1;
        return route[top+1];
    }
    return -1;
}

int main()
{
    int i, j, minValue, nodeNumber;
    for (i = 0; i < N_NODE; i++)
        for (j = 0; j < N_NODE; j++)
            w[i][j] = MAX_VALUE;
    w[0][1] = 10;
    w[0][2] = 3;
    w[0][3] = 20;
    w[1][3] = 5;
    w[2][1] = 2;
    w[2][3] = 10;
    w[2][4] = 15;
    w[3][4] = 11;
    for (i = 0; i < N_NODE; i++) {
        distance[i] = MAX_VALUE;
        status[i] = UNVISITED;
    }

    distance[start] = 0;
    print_status(-1);
    for (j = 0; j < datasize; j++) {
        minValue = MAX_VALUE;
        for (i = 0; i < datasize; i++) {
            if (status[i] == UNVISITED && minValue > distance[i]) {
                nodeNumber = i;
                minValue = distance[i];
            }
        }
        if (minValue == MAX_VALUE) {
            /* エラーメッセージを表示 */
            return 1;
        }
        status[nodeNumber] = VISITED;
        for (i = 0; i < datasize; i++) {
            if (status[i] == UNVISITED &&
                distance[i] > distance[nodeNumber] + w[nodeNumber][i]) {
                distance[i] = distance[nodeNumber] + w[nodeNumber][i];
                previous[i] = nodeNumber;
            }
        }
        print_status(j);
    }

    for (i = 0; i < datasize; i++) {
        push(i);
        j = i;
        while (j != start) {
            j = previous[j];
            push(j);
        }
        j = pop();
        while (j != -1) {
            printf("%c ", 'A' + j);
            j = pop();
        }
        putchar('\n');
    }

    return 0;
}