#include <stdio.h>
#define N 10
#define M 9999 /* 長い距離 */
#define SHOWENDONLY /* コメントアウトするとSをスタートとする全ての最短経路を表示 */
int main(void)
{
char *node = "ABCDEFGHIS";
/* データは隣接行列とする(有向グラフ) */
int graph[N + 1][N + 1] = {
/* A B C D E F G H I S */
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, M, M, M, 3, 6, M, 1, M, M}, /* A→ */
{0, M, 0, 2, M, M, M, M, M, M, 1}, /* B→ */
{0, M, 2, 0, 3, M, M, M, 8, M, M}, /* C→ */
{0, M, M, 3, 0, M, M, M, M, 1, M}, /* D→ */
{0, 3, M, M, M, 0, 2, M, M, M, M}, /* E→ */
{0, 6, M, M, M, 2, 0, 2, M, M, M}, /* F→ */
{0, M, M, M, M, M, 2, M, M, M, M}, /* G→ */
{0, 1, M, 8, M, M, M, M, M, 2, M}, /* H→ */
{0, M, M, M, 1, M, M, M, 2, M, M}, /* I→ */
{M, M, 1, M, M, M, M, M, M, M, M}, /* S→ */
};
int j, k, p, start, end, min, leng[N + 1], v[N + 1], index[N + 1], dist;
start = 10; /* S */
end = 7; /* G */
for (k = 1; k <= N; k++) {
leng[k] = M;
v[k] = 0;
}
leng[start] = index[start] = 0;
for (j = 1; j <= N; j++) {
min = M;
for (k = 1; k <= N; k++)
if (v[k] == 0 && leng[k] < min) {
p = k;
min = leng[k];
}
v[p] = 1;
if (min == M) {
printf("ルートを発見できませんでした。\n");
return 1;
}
for (k = 1; k <= N; k++)
if ((leng[p] + graph[p][k]) < leng[k]) {
leng[k] = leng[p] + graph[p][k];
index[k] = p;
}
}
for (j = 1; j <= N; j++) {
dist = leng[j];
#ifdef SHOWENDONLY
if (j == end)
#endif
printf("%c(%d)", node[j - 1], dist);
p = j;
while (index[p] != 0) {
dist -= graph[index[p]][p];
#ifdef SHOWENDONLY
if (j == end)
#endif
printf("<-%c(%d)", node[index[p] - 1], dist);
p = index[p];
}
#ifdef SHOWENDONLY
if (j == end)
#endif
printf("\n");
}
return 0;
}