dijkstra最短路径算法c

下面是Dijkstra最短路径算法的C语言实现代码，假设图的顶点编号从0开始：

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

#define MAX_VERTICES 1000

int graph[MAX_VERTICES][MAX_VERTICES]; // 存储图的邻接矩阵
int distance[MAX_VERTICES]; // 存储源点到各顶点的最短距离
int visited[MAX_VERTICES]; // 记录顶点是否已被访问

int dijkstra(int n, int source, int destination) {
    // 初始化
    for (int i = 0; i < n; i++) {
        distance[i] = INT_MAX;
        visited[i] = 0;
    }
    distance[source] = 0;

    // 运行 n 次，每次确定一个顶点的最短路径
    for (int i = 0; i < n; i++) {
        int min_distance = INT_MAX;
        int u = -1;
        // 选择当前未被访问的距离源点最近的顶点
        for (int j = 0; j < n; j++) {
            if (!visited[j] && distance[j] < min_distance) {
                u = j;
                min_distance = distance[j];
            }
        }
        // 如果找不到这样的顶点，则说明剩下的顶点和源点不连通，算法结束
        if (u == -1) {
            break;
        }
        visited[u] = 1;
        // 用刚刚找到的顶点更新其它顶点的距离
        for (int v = 0; v < n; v++) {
            if (!visited[v] && graph[u][v] != 0 && distance[u] + graph[u][v] < distance[v]) {
                distance[v] = distance[u] + graph[u][v];
            }
        }
    }
    return distance[destination];
}

int main() {
    int n, m, source, destination;
    scanf("%d %d %d %d", &n, &m, &source, &destination);
    // 读入图的边
    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;
    }
    int shortest_distance = dijkstra(n, source, destination);
    printf("%d\n", shortest_distance);
    return 0;
}

其中，`graph`数组存储图的邻接矩阵，`distance`数组存储源点到各顶点的最短距离，`visited`数组记录顶点是否已被访问，`dijkstra`函数实现Dijkstra算法，返回源点到目标顶点的最短距离。在 `main` 函数中，先读入图的边，然后调用 `dijkstra` 函数计算最短路径，最后输出结果。