codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#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 0 struct route { int nodenum; struct route *next; }; void add_list(struct route **node, int p) { struct route *n; assert(node != NULL); if ((n = malloc(sizeof(struct route))) != NULL) { n->nodenum = p; n->next = *node; *node = n; } } 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() { struct route *rvs, *p; int point, t, i, 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 { 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 + 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); flag = 1; /* need or not need? */ } } } 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'); } */ rvs = NULL; for (i = END; i != START; i = (nodedata[i].list)->nodenum) add_list(&rvs, i); printf("V0"); for (p = rvs; p != NULL; p = p->next) printf(" --> V%d", p->nodenum); putchar('\n'); printf("sum of weight: %d\n", nodedata[END].dist); clear_list(&rvs); for (i = 0; i < N; i++) clear_list(&(nodedata[i].list)); return 0; } /* end */
Private
[
?
]
Run code
Submit