无向图最短路径c语言代码

以下是使用 Dijkstra 算法求解无向图最短路径的 C 语言代码示例：

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

#define MAX_VERTICES 1000
#define INF INT_MAX

int graph[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵表示图
int dist[MAX_VERTICES];                // 记录每个顶点到源点的最短距离
bool visited[MAX_VERTICES];            // 记录每个顶点是否已被访问

int dijkstra(int n, int s, int t) {
    // 初始化
    for (int i = 0; i < n; i++) {
        dist[i] = INF;
        visited[i] = false;
    }
    dist[s] = 0;

    // 迭代 n 次
    for (int i = 0; i < n; i++) {
        int u = -1;
        int min_dist = INF;
        // 找到未访问的顶点中距离源点最近的顶点
        for (int j = 0; j < n; j++) {
            if (!visited[j] && dist[j] < min_dist) {
                u = j;
                min_dist = dist[j];
            }
        }
        if (u == -1) break;
        visited[u] = true;

        // 更新 u 的邻居顶点的最短距离
        for (int v = 0; v < n; v++) {
            if (!visited[v] && graph[u][v] != INF && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }

    return dist[t];
}

int main() {
    // 初始化邻接矩阵
    int n, m; // n 表示顶点个数，m 表示边的条数
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            graph[i][j] = INF;
        }
    }
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w); // 顶点 u 和顶点 v 之间有一条权值为 w 的边
        graph[u][v] = graph[v][u] = w;
    }

    // 求解最短路径
    int s, t; // 源点 s 和目标点 t
    scanf("%d %d", &s, &t);
    int shortest_dist = dijkstra(n, s, t);
    printf("The shortest path from %d to %d is %d.", s, t, shortest_dist);

    return 0;
}

该代码使用了邻接矩阵表示图，时间复杂度为 O(n^2)。如果使用邻接表表示图，时间复杂度可以优化到 O(ElogV)。