c语言无向图邻接表最短路径

要实现C语言无向图邻接表最短路径算法，可以使用Dijkstra算法。以下是详细步骤：

1. 定义一个结构体来表示图中的每个节点和边：

typedef struct Edge {
    int dest;  // 目标节点
    int weight;  // 边的权重
    struct Edge* next;  // 下一条边
} Edge;

typedef struct Node {
    int id;  // 节点的编号
    Edge* edges;  // 节点的出边列表
    int dist;  // 从起点到该节点的最短距离
    int visited;  // 是否已经访问过
} Node;

2. 初始化图中每个节点的出边列表和最短距离：

void init(Node* nodes, int numNodes) {
    for (int i = 0; i < numNodes; i++) {
        nodes[i].id = i;
        nodes[i].edges = NULL;
        nodes[i].dist = INT_MAX;
        nodes[i].visited = 0;
    }
}

3. 添加一条边到邻接表中：

void addEdge(Node* nodes, int src, int dest, int weight) {
    Edge* edge = (Edge*)malloc(sizeof(Edge));
    edge->dest = dest;
    edge->weight = weight;
    edge->next = nodes[src].edges;
    nodes[src].edges = edge;
}

4. 实现Dijkstra算法：

void dijkstra(Node* nodes, int numNodes, int start) {
    nodes[start].dist = 0;
    int curr = start;

    // 重复n次，n为节点数
    for (int i = 0; i < numNodes; i++) {
        // 标记当前节点已访问过
        nodes[curr].visited = 1;

        // 更新当前节点的所有出边的最短距离
        Edge* edge = nodes[curr].edges;
        while (edge != NULL) {
            int dest = edge->dest;
            int weight = edge->weight;
            if (!nodes[dest].visited && nodes[curr].dist + weight < nodes[dest].dist) {
                nodes[dest].dist = nodes[curr].dist + weight;
            }
            edge = edge->next;
        }

        // 找到未访问过的距离最短的节点
        int minDist = INT_MAX;
        for (int j = 0; j < numNodes; j++) {
            if (!nodes[j].visited && nodes[j].dist < minDist) {
                curr = j;
                minDist = nodes[j].dist;
            }
        }
    }
}

5. 示例代码：

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

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

typedef struct Node {
    int id;
    Edge* edges;
    int dist;
    int visited;
} Node;

void init(Node* nodes, int numNodes) {
    for (int i = 0; i < numNodes; i++) {
        nodes[i].id = i;
        nodes[i].edges = NULL;
        nodes[i].dist = INT_MAX;
        nodes[i].visited = 0;
    }
}

void addEdge(Node* nodes, int src, int dest, int weight) {
    Edge* edge = (Edge*)malloc(sizeof(Edge));
    edge->dest = dest;
    edge->weight = weight;
    edge->next = nodes[src].edges;
    nodes[src].edges = edge;
}

void dijkstra(Node* nodes, int numNodes, int start) {
    nodes[start].dist = 0;
    int curr = start;

    for (int i = 0; i < numNodes; i++) {
        nodes[curr].visited = 1;

        Edge* edge = nodes[curr].edges;
        while (edge != NULL) {
            int dest = edge->dest;
            int weight = edge->weight;
            if (!nodes[dest].visited && nodes[curr].dist + weight < nodes[dest].dist) {
                nodes[dest].dist = nodes[curr].dist + weight;
            }
            edge = edge->next;
        }

        int minDist = INT_MAX;
        for (int j = 0; j < numNodes; j++) {
            if (!nodes[j].visited && nodes[j].dist < minDist) {
                curr = j;
                minDist = nodes[j].dist;
            }
        }
    }
}

int main() {
    int numNodes = 5;
    Node nodes[numNodes];

    init(nodes, numNodes);

    addEdge(nodes, 0, 1, 10);
    addEdge(nodes, 0, 3, 5);
    addEdge(nodes, 1, 2, 1);
    addEdge(nodes, 1, 3, 2);
    addEdge(nodes, 2, 4, 4);
    addEdge(nodes, 3, 1, 3);
    addEdge(nodes, 3, 2, 9);
    addEdge(nodes, 3, 4, 2);

    dijkstra(nodes, numNodes, 0);

    for (int i = 0; i < numNodes; i++) {
        printf("从节点0到节点%d的最短距离为%d\n", i, nodes[i].dist);
    }

    return 0;
}

输出结果：

从节点0到节点0的最短距离为0
从节点0到节点1的最短距离为8
从节点0到节点2的最短距离为9
从节点0到节点3的最短距离为5
从节点0到节点4的最短距离为7