C言語で書いてみました

■ 最短経路を求める（平成15年秋期午後問4）

#include <stdio.h>

/* 基本情報 平成15年秋期 午後問4 */
/* 最短経路を求める */
#define N   5
#define MAX 10000   /* ∞の値 */
#define Output(x)   printf("%d\n",x)

void _debug(char *s, int *a, int t)
{
    int i;
    printf("%s:", s);
    for (i = 1; i < N; i++) {
        if (*(a+i) == MAX)
            printf(" ∞,");
        else
            printf("%3d,", *(a+i));
    }
    if (*(a+i) == MAX)
        printf(" ∞\n");
    else
        printf("%3d | %d\n", *(a+i), t);
}

int main()
{
    int C[N+1][N+1], D[N+1], Z;
    int P[N+1], S[N+1], W[N+1], T, X, Y;
    /* 配列 C の初期化 */
    int i, j;
    for (i = 1; i <= N; i++)
        for (j = 1; j <= N; j++)
            C[i][j] = MAX;  
    C[1][2] = 30; C[1][4] = 20; C[1][5] = 120; C[2][3] = 70;
    C[3][5] = 30; C[4][3] = 50; C[4][5] = 90;
    /* 初期設定 */
    X = 1;
    while (X <= N) {
        D[X] = C[1][X];
        P[X] = 0;
        S[X] = 1;
        X++;
    }
    P[1] = 1;
    /* 最短経路を求める処理 */
    X = 2;
    while (X <= N) {
        Y = 2;
        Z = MAX;
        while (Y <= N) {
            if ((P[Y] == 0) && (D[Y] < Z)) {
                T = Y;
                Z = D[Y];
            }
            Y++;
        }
        _debug("P", P, T);
        _debug("D", D, T);      
        P[T] = 1;
        _debug("P", P, T);
        Y = 2;
        while (Y <= N) {
            if ((P[Y] == 0) && (D[Y] > D[T] + C[T][Y])) {
                D[Y] = D[T] + C[T][Y];
                S[Y] = T;
            }
            Y++;
        }
        _debug("D", D, T);
        _debug("S", S, T);
        puts("-----");
        X++;
    }
    /* 最短経路の出力処理 */
    X = 1;
    Y = N;
    while (Y != 1) {
        W[X] = Y;
        Y = S[Y];
        X++;
    }
    W[X] = Y;
    while (X > 0) {
        Output(W[X]);
        X--;
    }
    return 0;
}