#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define N 14 /* 頂点の数*/
#define START 0 /* 始点の頂点番号*/
#define END 6 /* 終点の頂点番号*/
int g[N][N] = { /* グラフG はN 行N 列の配列*/
/* 0 1 2 3 4 5 6 7 8 9 10 11 12 13 */
{ 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0},
{ -1, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
{ 0, -2, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0},
{ 0, 0, -5, 0, 8, 0, 0, 0, 0, 0, 0, 0, -8, -1},
{ 0, 0, 0, -8, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0},
{ 0, 0, 0, 0, -2, 0, 1, 0, -6, 0, 0, 0, -2, 0},
{ 0, 0, 0, 0, 0, -1, 0, -2, 0, 0, 0, 0, 0, 0},
{ 0, 0, 0, 0, 0, 0, 2, 0, -1, 0, 0, 0, 0, 0},
{ 0, 0, 0, 0, 0, 6, 0, 1, 0, -5, 0, 0, 0, -3},
{ 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, -2, -3, 7, 1},
{ -3, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 6, 0, 0},
{ 0, -1, 0, 0, 0, 0, 0, 0, 0, 3, -6, 0, 5, 0},
{ 0, 0, -4, 8, 0, 2, 0, 0, 0, -7, 0, -5, 0, 1},
{ 0, 0, 0, 1, 0, 0, 0, 0, 3, -1, 0, 0, -1, 0}
};
#define INIT 10000
struct route {
int nodenum;
struct route *next;
};
void add_list(struct route **node, int p) {
struct route *n;
assert(node != NULL);
if (*node == NULL) {
if ((n = malloc(sizeof(struct route))) != NULL) {
n->nodenum = p;
n->next = NULL;
*node = n;
}
} else {
add_list(&((*node)->next), p);
}
}
void clear_list(struct route **node) {
if (*node == NULL)
return;
if ((*node)->next != NULL)
clear_list(&((*node)->next));
free(*node);
*node = NULL;
}
void print_list(struct route *node) {
if (node != NULL) {
printf("<%d>, ", node->nodenum);
print_list(node->next);
}
}
struct nodedata {
int tocheck;
int dist;
struct route *list;
} nodedata[N];
int main() {
int i;
int flag;
for (i = 0; i < N; i++) {
nodedata[i].tocheck = 0;
nodedata[i].dist = INIT;
nodedata[i].list = NULL;
}
nodedata[START].tocheck = 1;
nodedata[START].dist = 0;
do {
int point, t;
flag = 0;
for (point = 0; point < N; point++) {
if (nodedata[point].tocheck > 0) {
for (i = 0; i < N; i++) {
if (g[point][i] != 0) {
if ((t = nodedata[point].dist + abs(g[point][i])) < nodedata[i].dist) {
clear_list(&(nodedata[i].list));
nodedata[i].dist = t;
add_list(&(nodedata[i].list), point);
nodedata[i].tocheck = 1;
flag = 1;
} else if (t == nodedata[i].dist) {
add_list(&(nodedata[i].list), point);
}
}
}
nodedata[point].tocheck = 0;
}
}
} while (flag > 0);
for (i = 0; i < N; i++) {
printf("node %d: dist = %d: ", i, nodedata[i].dist);
print_list(nodedata[i].list);
putchar('\n');
}
for (i = END; i != START; i = (nodedata[i].list)->nodenum)
printf("node %d(%d) <- ", i, nodedata[i].dist);
printf("node %d(%d)\n", i, nodedata[i].dist);
for (i = 0; i < N; i++)
clear_list(&(nodedata[i].list));
return 0;
}
/* end */