dijkstra算法c语言

Dijkstra算法是一种求解带权图最短路径的贪心算法，它的基本思想是从起点开始，每次选择当前最短路径的节点来扩展，直到找到终点或者所有节点都被扩展过。

以下是Dijkstra算法的C语言实现：

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

#define INF 0x3f3f3f3f

int n, m; // 图的节点数和边数
int edge[1001][1001]; // 保存边的权重
int dis[1001]; // 保存起点到每个节点的最短路径长度
bool vis[1001]; // 标记节点是否已经被扩展过

// 找到当前未被扩展的距离起点最近的节点
int find_min_node() {
    int min_dis = INF, min_node = -1;
    for (int i = 1; i <= n; i++) {
        if (!vis[i] && dis[i] < min_dis) {
            min_dis = dis[i];
            min_node = i;
        }
    }
    return min_node;
}

void dijkstra(int s) {
    // 初始化
    for (int i = 1; i <= n; i++) {
        dis[i] = INF;
        vis[i] = false;
    }
    dis[s] = 0;

    // 扩展n次，即每个节点都被扩展过一次
    for (int i = 1; i <= n; i++) {
        int u = find_min_node();
        vis[u] = true;
        // 更新与u相邻的节点的最短路径长度
        for (int v = 1; v <= n; v++) {
            if (!vis[v] && edge[u][v] != INF && dis[u] + edge[u][v] < dis[v]) {
                dis[v] = dis[u] + edge[u][v];
            }
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    // 初始化边的权重为INF
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            edge[i][j] = INF;
        }
    }
    // 读入边的权重
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        edge[u][v] = edge[v][u] = w;
    }
    // 求起点到每个节点的最短路径长度
    dijkstra(1);
    // 输出结果
    for (int i = 1; i <= n; i++) {
        printf("%d ", dis[i]);
    }
    return 0;
}

该实现使用邻接矩阵存储边的权重，时间复杂度为O(n^2)，适用于稠密图。如果使用邻接表存储边，则时间复杂度可以优化到O(mlogn)，适用于稀疏图。