dijkstra.c

#include <limits.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

#define NMAX 100

typedef struct visit visit;
struct visit {
    bool *visited;
    int *distance, *prev;
    int n;
};

typedef struct weight weight;
struct weight {
    int *weight;
    int n;
};

static void clear_visit(visit *);
static void clear_weight(weight *);
static void controller(weight *);
static void dijkstra(weight *, visit *);
static inline int get_distance(visit *, int, int);
static inline int get_prev(visit *, int, int);
static inline bool get_visited(visit *, int, int);
static inline int get_weight(weight *, int, int);
static visit *init_visit(int);
static weight *read_weight(void);
static inline void set_distance(visit *, int, int, int);
static inline void set_prev(visit *, int, int, int);
static inline void set_visited(visit *, int, int, bool);
static inline void set_weight(weight *, int, int, int);
static void show_from_to(visit *, int, int);
static void show_visit(visit *);
static void show_weight(weight *);

static inline bool get_visited(visit *visit, int x, int y) {
    return visit->visited[x * visit->n + y];
}

static inline void set_visited(visit *visit, int x, int y, bool v) {
    visit->visited[x * visit->n + y] = v;
}

static inline int get_distance(visit *visit, int x, int y) {
    return visit->distance[x * visit->n + y];
}

static inline void set_distance(visit *visit, int x, int y, int v) {
    visit->distance[x * visit->n + y] = v;
}

static inline int get_prev(visit *visit, int x, int y) {
    return visit->prev[x * visit->n + y];
}

static inline void set_prev(visit *visit, int x, int y, int v) {
    visit->prev[x * visit->n + y] = v;
}

static inline int get_weight(weight *weight, int x, int y) {
    return weight->weight[x * weight->n + y];
}

static inline void set_weight(weight *weight, int x, int y, int v) {
    weight->weight[x * weight->n + y] = v;
}

static void show_weight(weight *weight) {
    puts("data:");
    for (int i = 1; i <= weight->n; i++) {
        for (int j = 1; j <= weight->n; j++) {
            if (get_weight(weight, i, j) < INT_MAX) {
                printf("%3d", get_weight(weight, i, j));
            } else {
                printf("  x");
            }
        }
        puts("");
    }
    puts("");
}

static weight *read_weight(void) {
    int n;
    if (scanf("%d%*[^\n]", &n) != 1 || n > NMAX) {
        return NULL;
    }
    weight *weight = calloc(sizeof(*weight), 1);
    weight->n = n;
    weight->weight = calloc(sizeof(*(weight->weight)), (n + 1) * (n + 1));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            set_weight(weight, i, j, INT_MAX);
        }
    }
    int x, y, v;
    while (scanf("%d%d%d%*[^\n]", &x, &y, &v) == 3) {
        set_weight(weight, x, y, v);
        set_weight(weight, y, x, v);
    }
    show_weight(weight);
    return weight;
}

static visit *init_visit(int n) {
    int nn = (n + 1) * (n + 1);
    visit *visit = calloc(sizeof(*visit), 1);
    visit->n = n;
    visit->visited = calloc(sizeof(*(visit->visited)), nn);
    visit->distance = calloc(sizeof(*(visit->distance)), nn);
    visit->prev = calloc(sizeof(*(visit->prev)), nn);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            set_visited(visit, i, j, false);
            set_distance(visit, i, j, INT_MAX);
        }
    }
    return visit;
}

static void clear_visit(visit *visit) {
    free(visit->visited);
    free(visit->distance);
    free(visit->prev);
    free(visit);
}

static void clear_weight(weight *weight) {
    free(weight->weight);
    free(weight);
}

static void show_visit(visit *visit) {
    for (int start = 1; start <= visit->n; start++) {
        for (int i = 1; i <= visit->n; i++) {
            int d = 0;
            for (int j = i; j != start && get_visited(visit, start, j);
                    j = get_prev(visit, start, j)) {
                d += get_distance(visit, start, j);
                printf("%d <- ", j);
            }
            printf("%d (%d)\n", start, d);
        }
        puts("");
    }
}

static void show_from_to(visit *visit, int from, int to) {
    int d = 0;
    for (int i = to; i != from && get_visited(visit, from, i);
            i = get_prev(visit, from, i)) {
        d += get_distance(visit, from, i);
        printf("%d <- ", i);
    }
    printf("%d (%d)\n\n", from, d);
}

static void controller(weight *weight) {
    visit *visit = init_visit(weight->n);
    dijkstra(weight, visit);
    show_visit(visit);
    for (int i = 1; i <= weight->n; i++) {
        for (int j = i + 1; j <= weight->n; j++) {
            show_from_to(visit, i, j);
        }
    }
    clear_visit(visit);
}

static void dijkstra(weight *weight, visit *visit) {
    for (int start = 1, min; start <= weight->n; start++) {
        int next = start;
        set_distance(visit, start, next, 0);
        do {
            int i = next;
            min = INT_MAX;
            set_visited(visit, start, i, true);
            for (int j = 1; j <= weight->n; j++) {
                if (get_visited(visit, start, j)) {
                    continue;
                }
                if (get_weight(weight, i, j) < INT_MAX
                        && get_distance(visit, start, i) + get_weight(weight, i, j)
                        < get_distance(visit, start, j)) {
                    set_distance(visit, start, j,
                            get_distance(visit, start, i) + get_weight(weight, i, j));
                    set_prev(visit, start, j, i);
                }
                if (get_distance(visit, start, j) < min) {
                    min = get_distance(visit, start, j);
                    next = j;
                }
            }
        } while (min < INT_MAX);
    }
}

int main(void) {
    weight *weight = read_weight();
    controller(weight);
    clear_weight(weight);
    return EXIT_SUCCESS;
}