迪杰斯特拉算法c语言

以下是迪杰斯特拉算法的C语言实现：

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

// 定义图的最大节点数
#define NODE_NUM 6

// 定义邻接矩阵表示的图
int graph[NODE_NUM][NODE_NUM] = {
    {0, 2, 4, 1, 0, 0},
    {2, 0, 0, 3, 10, 0},
    {4, 0, 0, 2, 0, 5},
    {1, 3, 2, 0, 7, 8},
    {0, 10, 0, 7, 0, 0},
    {0, 0, 5, 8, 0, 0}
};

// 执行迪杰斯特拉算法
void dijkstra(int start) {
    // 初始化距离和标记数组
    int dist[NODE_NUM];
    int visited[NODE_NUM];
    for(int i = 0; i < NODE_NUM; i++) {
        dist[i] = INT_MAX;
        visited[i] = 0;
    }
    dist[start] = 0;
    
    // 循环遍历所有节点
    for(int i = 0; i < NODE_NUM; i++) {
        // 找到距离起点最近的节点
        int min_dist = INT_MAX, min_index = -1;
        for(int j = 0; j < NODE_NUM; j++) {
            if(!visited[j] && dist[j] < min_dist) {
                min_dist = dist[j];
                min_index = j;
            }
        }
        // 标记该节点已访问
        visited[min_index] = 1;
        // 更新该节点的邻居节点的距离
        for(int j = 0; j < NODE_NUM; j++) {
            if(graph[min_index][j] && dist[min_index] != INT_MAX && dist[min_index] + graph[min_index][j] < dist[j]) {
                dist[j] = dist[min_index] + graph[min_index][j];
            }
        }
    }
    // 输出最短路径
    printf("从节点%d出发到各节点的最短路径长度为：\n", start);
    for(int i = 0; i < NODE_NUM; i++) {
        printf("到节点%d的最短路径长度为：%d\n", i, dist[i]);
    }
}

int main() {
    // 从节点0出发执行迪杰斯特拉算法
    dijkstra(0);
    return 0;
}

以上实现采用邻接矩阵表示图，使用了一个数组dist来记录起点到各个节点的最短距离，使用一个数组visited来记录是否访问过某个节点。在遍历所有节点的过程中，每次找到距离起点最近的节点，标记该节点已访问，并更新该节点的所有邻居节点的距离。最后输出起点到各个节点的最短距离。