Let's write β

プログラミング中にできたことか、思ったこととか

Floydのアルゴリズム

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