无向图 求最短路径C语言实现

求无向图的最短路径可以使用Dijkstra算法，其基本思想是从起点开始，每次选择当前最短路径的节点进行扩展，直到扩展到终点或者无法继续扩展为止。

以下是一份C语言实现的示例代码：

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

#define MAX_VERTICES 1000
#define INF INT_MAX

typedef struct {
    int dest;
    int weight;
    struct EdgeNode* next;
} EdgeNode;

typedef struct {
    EdgeNode* head;
} VertexNode;

VertexNode graph[MAX_VERTICES];
int dist[MAX_VERTICES];
int visited[MAX_VERTICES];

void addEdge(int src, int dest, int weight) {
    EdgeNode* newNode = (EdgeNode*)malloc(sizeof(EdgeNode));
    newNode->dest = dest;
    newNode->weight = weight;
    newNode->next = graph[src].head;
    graph[src].head = newNode;
}

int getMinDistVertex(int n) {
    int minDist = INF;
    int minIndex = -1;
    for (int i = 0; i < n; i++) {
        if (!visited[i] && dist[i] < minDist) {
            minDist = dist[i];
            minIndex = i;
        }
    }
    return minIndex;
}

void dijkstra(int n, int src) {
    for (int i = 0; i < n; i++) {
        dist[i] = INF;
        visited[i] = 0;
    }
    dist[src] = 0;
    for (int i = 0; i < n-1; i++) {
        int u = getMinDistVertex(n);
        visited[u] = 1;
        EdgeNode* p = graph[u].head;
        while (p != NULL) {
            int v = p->dest;
            if (!visited[v] && dist[u] != INF && dist[u] + p->weight < dist[v]) {
                dist[v] = dist[u] + p->weight;
            }
            p = p->next;
        }
    }
}

int main() {
    int n, m; // n为节点数，m为边数
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        int src, dest, weight;
        scanf("%d%d%d", &src, &dest, &weight);
        addEdge(src, dest, weight);
        addEdge(dest, src, weight);
    }
    dijkstra(n, 0);
    for (int i = 0; i < n; i++) {
        printf("dist[%d] = %d\n", i, dist[i]);
    }
    return 0;
}

其中，`graph`数组用来存储图的邻接表表示，`dist`数组用来存储从起点到每个节点的最短路径长度，`visited`数组用来标记每个节点是否已经被访问过。`addEdge`函数用来添加边，`getMinDistVertex`函数用来获取当前未访问节点中距离起点最近的节点，`dijkstra`函数用来执行Dijkstra算法，最后输出每个节点到起点的最短路径长度。