Dijkstraも書いたのですが、そちらはコードの量が多いので割愛。
FloydのアルゴリズムをCで実装
/* * map.h */ #ifndef _MAP_H_ #define _MAP_H_ #include <limits.h> #ifndef INF #define INF (INT_MAX / 2) #endif struct map { int size; int **data; }; struct map* readmap(char*); void show_map(struct map*); void free_map(struct map*); #endif /* * map.c */ #include <stdio.h> #include <stdlib.h> #include <limits.h> #include "map.h" struct map* readmap(char *mapfile_name) { FILE *mapfile; struct map* m; int i, j; if((mapfile = fopen(mapfile_name, "r")) == NULL) { fprintf(stderr, "Failed to open file %s\n", mapfile_name); return NULL; } if((m = (struct map*)malloc(sizeof(struct map))) == NULL) { fprintf(stderr, "Failed to allocate map.\n"); return NULL; } fscanf(mapfile, "%d", &m->size); if((m->data = (int **)malloc(sizeof(int *) * m->size)) == NULL) { fprintf(stderr, "Failed to allocate map data array.\n"); free(m); return NULL; } for(i = 0; i < m->size; i++) { if((m->data[i] = (int *)malloc(sizeof(int) * m->size)) == NULL) { fprintf(stderr, "Failed to allocate map data array.\n"); return NULL; } } for(i = 0; i < m->size; i++) { for(j = 0; j < m->size; j++) { fscanf(mapfile,"%d", &m->data[i][j]); if(m->data[i][j] < 0) m->data[i][j] = INF; } } fclose(mapfile); return m; } void show_map(struct map *m) { int i, j; for(i = 0; i < m->size; i++) { for(j = 0; j < m->size; j++) { printf("[%d]", m->data[i][j]); } putchar('\n'); } } void free_map(struct map *m) { int i; for(i = 0; i < m->size; i++) { free(m->data[i]); } free(m->data); free(m); } /* * main.c */ #include <stdio.h> #include <stdlib.h> #include "map.h" int** floyd(struct map*); int main(int argc, char** argv) { int **a; int i, j; if(argc < 2) exit(1); struct map *m = readmap(argv[1]); show_map(m); a = floyd(m); for(i = 0; i < m->size; i++) { for(j = 0; j < m->size; j++) { printf("(%d, %d) -> %d\n", i, j, a[i][j]); } } for(i = 0; i < m->size; i++) { free(a[i]); } free_map(m); free(a); return 0; } int** floyd(struct map* m) { int **a; int i,j,k; if((a = (int **)malloc(sizeof(int *) * m->size)) == NULL) { fprintf(stderr, "Failed to allocate array\n"); return NULL; } for(i = 0; i < m->size; i++) { if((a[i] = (int *)malloc(sizeof(int) * m->size)) == NULL) { fprintf(stderr, "Failed to allocate array.\n"); free(a); return NULL; } } //Floyd for(i = 0; i < m->size; i++) { for(j = 0; j < m->size; j++) { a[i][j] = m->data[i][j]; } } for(k = 0; k < m->size; k++) for(i = 0; i < m->size; i++) for(j = 0; j < m->size; j++) if((a[i][k] + a[k][j]) < a[i][j]) a[i][j] = a[i][k] + a[k][j]; return a; }
こんなグラフのデータをつくって(接続していない所は負値で表現)
3 0 -1 3 -1 0 1 3 1 -0
./a.out graph.dat [0][1073741823][3] [1073741823][0][1] [3][1][0] (0, 0) -> 0 (0, 1) -> 4 (0, 2) -> 3 (1, 0) -> 4 (1, 1) -> 0 (1, 2) -> 1 (2, 0) -> 3 (2, 1) -> 1 (2, 2) -> 0