用C语言实现迪杰斯特拉算法

迪杰斯特拉算法（Dijkstra's algorithm）是一种用于计算带权有向图的最短路径的算法。这里是用 C 语言实现迪杰斯特拉算法的示例代码：

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

// 定义图的最大大小
#define MAX_SIZE 100

// 定义一个结构体表示图的边
struct Edge {
    int u; // 起始节点
    int v; // 目标节点
    int weight; // 边的权重
};

// 定义一个结构体表示图
struct Graph {
    int n; // 节点数量
    int m; // 边数量
    struct Edge edges[MAX_SIZE]; // 边列表
};

// 初始化图
void initGraph(struct Graph *g, int n, int m, int u[], int v[], int weight[]) {
    g->n = n;
    g->m = m;
    for (int i = 0; i < m; i++) {
        g->edges[i].u = u[i];
        g->edges[i].v = v[i];
        g->edges[i].weight = weight[i];
    }
}

// 迪杰斯特拉算法
void dijkstra(struct Graph *g, int start, int dist[]) {
    // 初始化距离数组
    for (int i = 0; i < g->n; i++) {
        dist[i] = INT_MAX;
    }
    dist[start] = 0;

    // 初始化已访问数组
    int visited[MAX_SIZE] = { 0 };

    // Dijkstra算法主循环
    for (int i = 0; i < g->n; i++) {
        // 找到距离起点最近的节点
        int minDist = INT_MAX;
        int u = -1;
        for (int j = 0; j < g->n; j++) {
            if (!visited[j] && dist[j] < minDist) {
                minDist = dist[j];
                u = j;
            }
        }

        // 标记该节点已经访问过
        visited[u] = 1;

        // 更新与该节点相邻的节点的距离
        for (int j = 0; j < g->m; j++) {
            if (g->edges[j].u == u) {
                int v = g->edges[j].v;
                int weight = g->edges[j].weight;
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                }
            }
        }
    }
}

// 测试代码
int main() {
    int n = 5, m = 7;
    int u[] = {0, 0, 1, 1, 1, 2, 3};
    int v[] = {1, 2, 2, 3, 4, 3, 4};
    int weight[] = {10, 5, 1, 2, 4, 7, 3};

    struct Graph g;
    initGraph(&g, n, m, u, v, weight);

    int dist[MAX_SIZE];
    dijkstra(&g, 0, dist);

    printf("最短距离：\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", dist[i]);
    }
    printf("\n");

    return 0;
}

在上述代码中，我们定义了一个 `Edge` 结构体表示图的边，定义了一个 `Graph` 结构体表示图，实现了初始化图的函数 `initGraph` 和迪杰斯特拉算法的函数 `dijkstra`。在 `main` 函数中，我们定义了一个包含 5 个节点和 7 条边的有向图，并通过 `dijkstra` 函数计算了从节点 0 到其他节点的最短距离。