dijkstra 最短路径

train.c

#include <stdio.h>
#include <stdlib.h> /* malloc, on_exit */
#include <string.h> /* strerror, strcat */

#define E_OK 0
#define E_FAIL -1
#define E_NO_MEM -12

#define _FL_ __FILE__,__LINE__  /* For debug src:line number */

#define MAX_CITY_LEN 32

struct s_entry {
    char s[MAX_CITY_LEN];
    struct {
        struct s_entry *tqe_next;
        struct s_entry **tqe_prev;
    } entries;
};
struct listhead {
    struct s_entry *tqh_first;
    struct s_entry **tqh_last;
};

#define LINE_MAX 1024

struct idx_entry {
    int idx;
    struct {
        struct idx_entry *le_next;
        struct idx_entry **le_prev;
    } entries;
};
struct vertex_head {
    struct idx_entry *lh_first;
};
/**
 * The first line of the input contains N strings of station names, separated by comma ,.
 * @param head city strings linked list
 * @param path input file path
 * @return int vertex count
 */
int load_city_list(struct listhead* head) {
    struct s_entry* n1 = NULL;
    char line[LINE_MAX] = { 0x00 }, *p = line;
    char* q = p;
    int V = 0; /* Count cities */

    /* Initialize city linked list */
    head->tqh_first = NULL;
    head->tqh_last = &head->tqh_first;
    fgets(line, LINE_MAX, stdin);
    for (q = p; *p != '\r' && *p != '\n'; p++) {
        if (*p == ',') {
            *p = '\0';
            n1 = (struct s_entry *)malloc(sizeof(struct s_entry));
            strncpy(n1->s, q, 32);
            n1->entries.tqe_next = NULL;
            n1->entries.tqe_prev = head->tqh_last;
            *head->tqh_last = n1;
            head->tqh_last = &n1->entries.tqe_next;
            q = p + 1;
            V += 1;
        }
    }
    *p = '\0';
    /* rtrim '\r', '\n', ' ' */
    while (*(p - 1) == 0x0d || *(p - 1) == 0x0a || *(p - 1) == 0x20) {
        *p-- = 0x00;
    }
    n1 = (struct s_entry *)malloc(sizeof(struct s_entry));
    if (n1 == NULL) {
        return V;
    }
    strncpy(n1->s, q, 32);
    n1->entries.tqe_next = NULL;
    n1->entries.tqe_prev = head->tqh_last;
    *head->tqh_last = n1;
    head->tqh_last = &n1->entries.tqe_next;
    V += 1;
    return V;
}

void destroy_city_list(struct listhead* head) {
    struct s_entry* n2 = NULL;
    while (head->tqh_first != NULL) {
        n2 = head->tqh_first;
        if (n2->entries.tqe_next != NULL) {
            n2->entries.tqe_next->entries.tqe_prev = n2->entries.tqe_prev;
        } else {
            head->tqh_last = n2->entries.tqe_prev;
        }
        *n2->entries.tqe_prev = n2->entries.tqe_next;
        free(n2);
    }
}

/**
 * The following V lines is the distance matrix, and each line contains V cells that are separated by comma ,.
 * @param V
 * @return distance matrix
 */
int load_dist_graph(int* graph, int V) {
    char line[LINE_MAX] = { 0x00 }, * p;
    int i = 0, j = 0;
    int b = 0; /* For each distance */

    memset(graph, 0, V * V * sizeof(int));
    /* Scan V lines of distance matrix */
    for (i = 0; i < V; i++) {
        fgets(line, LINE_MAX, stdin);
        j = 0;
        for (p = line; *p != '\n' && *p != '\r'; p++) {
            if ('0' <= *p && *p <= '9') {
                b *= 10;
                b += *p - 0x30;
            }
            else if (*p == ',') {
                graph[i * V + j] = b;
                b = 0;
                j += 1;
            }
            else {
                return -1;
            }
        }
        graph[i * V + j] = b;
        b = 0;
    }

    return