用C语言以邻接表作存储结构实现求从源点到其余各顶点的最短路径的 Dijkstra 法

好的，下面是用 C 语言实现 Dijkstra 算法的代码，以邻接表作为存储结构：

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

#define MAX_VERTEX_NUM 100     // 图中顶点数的最大值

typedef struct EdgeNode {      // 邻接表中的边结点
    int adjvex;               // 邻接点在顶点数组中的下标
    int weight;               // 边的权值
    struct EdgeNode *next;    // 指向下一个邻接点的指针
} EdgeNode;

typedef struct VertexNode {    // 邻接表中的顶点结点
    int data;                 // 顶点的数据
    EdgeNode *firstEdge;      // 指向第一个邻接点的指针
} VertexNode, AdjList[MAX_VERTEX_NUM];

typedef struct {              // 邻接表存储的图
    AdjList adjList;          // 存储每个顶点的邻接表
    int vertexNum;            // 图中顶点的数量
    int edgeNum;              // 图中边的数量
} Graph;

void initGraph(Graph *graph) {
    int i;
    for (i = 0; i < MAX_VERTEX_NUM; i++) {
        graph->adjList[i].data = 0;
        graph->adjList[i].firstEdge = NULL;
    }
    graph->vertexNum = 0;
    graph->edgeNum = 0;
}

void addVertex(Graph *graph, int data) {
    graph->adjList[graph->vertexNum].data = data;
    graph->adjList[graph->vertexNum].firstEdge = NULL;
    graph->vertexNum++;
}

void addEdge(Graph *graph, int src, int dest, int weight) {
    EdgeNode *newEdge = (EdgeNode *) malloc(sizeof(EdgeNode));
    newEdge->adjvex = dest;
    newEdge->weight = weight;
    newEdge->next = graph->adjList[src].firstEdge;
    graph->adjList[src].firstEdge = newEdge;
    graph->edgeNum++;
}

void dijkstra(Graph *graph, int start, int *dist, int *prev) {
    bool visited[MAX_VERTEX_NUM] = {false};  // 标记每个顶点是否已经访问过
    int i, j, k, min;
    EdgeNode *p;
    for (i = 0; i < graph->vertexNum; i++) {
        dist[i] = INT_MAX;   // 到每个顶点的距离初始化为无穷大
        prev[i] = -1;        // 每个顶点的前驱顶点初始化为 -1
    }
    dist[start] = 0;         // 源点到自身的距离为 0
    for (i = 0; i < graph->vertexNum; i++) {
        min = INT_MAX;
        for (j = 0; j < graph->vertexNum; j++) {
            if (!visited[j] && dist[j] < min) {
                min = dist[j];
                k = j;
            }
        }
        visited[k] = true;   // 标记顶点 k 已经访问过
        for (p = graph->adjList[k].firstEdge; p != NULL; p = p->next) {
            j = p->adjvex;
            if (!visited[j] && dist[k] + p->weight < dist[j]) {
                dist[j] = dist[k] + p->weight;   // 更新源点到 j 的最短距离
                prev[j] = k;                     // j 的前驱顶点为 k
            }
        }
    }
}

int main() {
    Graph graph;
    initGraph(&graph);
    addVertex(&graph, 0);
    addVertex(&graph, 1);
    addVertex(&graph, 2);
    addVertex(&graph, 3);
    addEdge(&graph, 0, 1, 10);
    addEdge(&graph, 0, 3, 5);
    addEdge(&graph, 1, 2, 1);
    addEdge(&graph, 1, 3, 2);
    addEdge(&graph, 2, 3, 4);
    int dist[MAX_VERTEX_NUM];   // 存储源点到每个顶点的最短距离
    int prev[MAX_VERTEX_NUM];   // 存储每个顶点的前驱顶点
    dijkstra(&graph, 0, dist, prev);
    printf("源点到各顶点的最短距离：\n");
    int i;
    for (i = 0; i < graph.vertexNum; i++) {
        printf("%d ", dist[i]);
    }
    printf("\n各顶点的前驱顶点：\n");
    for (i = 0; i < graph.vertexNum; i++) {
        printf("%d ", prev[i]);
    }
    printf("\n");
    return 0;
}

其中，initGraph()、addVertex() 和 addEdge() 分别用于初始化图、添加顶点和添加边。

dijkstra() 函数用于求解从源点 start 到其余各顶点的最短路径。其中，dist 数组存储源点到每个顶点的最短距离，prev 数组存储每个顶点的前驱顶点。

在 main() 函数中，我们创建了一个包含 4 个顶点和 5 条边的图，并以顶点 0 为源点调用 dijkstra() 函数进行求解。

希望这个代码可以帮助到你。