C语言迪杰斯特拉算法输出航空最短路径完整代码

下面是一个 C 语言实现迪杰斯特拉算法输出航空最短路径的完整代码：

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

#define MAX_VERTICES 26
#define INF INT_MAX

typedef struct {
    int weight[MAX_VERTICES][MAX_VERTICES];
    int n;
} Graph;

void init_graph(Graph* g) {
    g->n = 0;
    for (int i = 0; i < MAX_VERTICES; i++) {
        for (int j = 0; j < MAX_VERTICES; j++) {
            g->weight[i][j] = INF;
        }
    }
}

void add_edge(Graph* g, int u, int v, int w) {
    g->weight[u][v] = w;
}

void dijkstra(Graph* g, int start, int end) {
    int distance[MAX_VERTICES];
    int visited[MAX_VERTICES];
    int previous[MAX_VERTICES];

    for (int i = 0; i < g->n; i++) {
        distance[i] = INF;
        visited[i] = 0;
        previous[i] = -1;
    }

    distance[start] = 0;

    for (int i = 0; i < g->n; i++) {
        int min_distance = INF;
        int u = -1;

        for (int j = 0; j < g->n; j++) {
            if (!visited[j] && distance[j] < min_distance) {
                min_distance = distance[j];
                u = j;
            }
        }

        if (u == -1) {
            break;
        }

        visited[u] = 1;

        for (int v = 0; v < g->n; v++) {
            if (g->weight[u][v] != INF) {
                int new_distance = distance[u] + g->weight[u][v];
                if (new_distance < distance[v]) {
                    distance[v] = new_distance;
                    previous[v] = u;
                }
            }
        }
    }

    printf("从 %c 到 %c 的最短路径为：", 'A' + start, 'A' + end);

    int path[MAX_VERTICES];
    int path_length = 0;

    for (int u = end; u != -1; u = previous[u]) {
        path[path_length++] = u;
    }

    for (int i = path_length - 1; i >= 0; i--) {
        printf("%c ", 'A' + path[i]);
        if (i > 0) {
            printf("- ");
        }
    }

    printf("，路径长度为 %d\n", distance[end]);
}

int main() {
    Graph g;
    init_graph(&g);
    g.n = 5;
    add_edge(&g, 0, 1, 5);
    add_edge(&g, 0, 2, 2);
    add_edge(&g, 1, 2, 1);
    add_edge(&g, 1, 3, 3);
    add_edge(&g, 2, 1, 3);
    add_edge(&g, 2, 3, 7);
    add_edge(&g, 2, 4, 4);
    add_edge(&g, 3, 4, 2);
    add_edge(&g, 4, 3, 1);

    dijkstra(&g, 0, 4);

    return 0;
}

在这个例子中，我们首先定义了一个结构体 `Graph`，它包含了一个二维数组 `weight`，表示每个节点之间的边权重，以及一个整数 `n`，表示节点的数量。然后我们实现了一些辅助函数，包括 `init_graph` 函数用于初始化图，`add_edge` 函数用于添加边，以及 `dijkstra` 函数用于执行迪杰斯特拉算法。

在 `main` 函数中，我们创建了一个包含 5 个节点的图，并使用 `add_edge` 函数添加了一些边。然后我们调用 `dijkstra` 函数，传入起点和终点的索引，输出最短路径和路径长度。在这个例子中，最短路径为 A - C - B - D，路径长度为 8。