dijkstra算法C语言代码

以下是使用C语言实现的Dijkstra算法代码，假设图的邻接矩阵已经定义为`graph[][]`，起点为`start`，终点为`end`，节点总数为`n`。

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

#define MAX_NODES 100
#define INF 1000000

int graph[MAX_NODES][MAX_NODES];
int dist[MAX_NODES];
bool visited[MAX_NODES];

int dijkstra(int start, int end, int n) {
    // 初始化距离数组和访问标记数组
    for (int i = 0; i < n; i++) {
        dist[i] = INF;
        visited[i] = false;
    }
    dist[start] = 0;
    // 循环n次，每次找到一个未访问节点中距离起点最近的节点
    for (int i = 0; i < n; i++) {
        int min_dist = INF, min_node = -1;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && dist[j] < min_dist) {
                min_dist = dist[j];
                min_node = j;
            }
        }
        // 如果找不到未访问节点，则退出循环
        if (min_node == -1) break;
        // 标记该节点为已访问
        visited[min_node] = true;
        // 更新与该节点相邻的未访问节点的距离
        for (int j = 0; j < n; j++) {
            if (!visited[j] && graph[min_node][j] != INF) {
                int new_dist = dist[min_node] + graph[min_node][j];
                if (new_dist < dist[j]) {
                    dist[j] = new_dist;
                }
            }
        }
    }
    // 返回起点到终点的最短距离
    return dist[end];
}

int main() {
    int n, m, start, end;
    scanf("%d%d%d%d", &n, &m, &start, &end);
    // 初始化图的邻接矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) {
                graph[i][j] = 0;
            } else {
                graph[i][j] = INF;
            }
        }
    }
    // 读入边的信息并更新邻接矩阵
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        graph[u][v] = graph[v][u] = w;
    }
    // 调用Dijkstra算法计算最短距离
    int shortest_dist = dijkstra(start, end, n);
    // 输出结果
    printf("%d\n", shortest_dist);
    return 0;
}

需要注意的是，如果图中存在负权边，则Dijkstra算法无法正确计算最短路径。此时可以使用Bellman-Ford算法或者SPFA算法来计算最短路径。