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

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

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

#define MAX_VERTEX 100  // 图的最大顶点数
#define INF INT_MAX     // 无穷大

// 定义邻接表中的结点
typedef struct node {
    int vertex;      // 目标顶点
    int weight;      // 权重
    struct node *next;  // 下一个邻接点
} Node;

// 定义邻接表
typedef struct graph {
    int V;           // 顶点数
    int E;           // 边数
    Node **adjList;  // 邻接表
} Graph;

// 初始化邻接表
Graph *initGraph(int V) {
    Graph *G = (Graph *) malloc(sizeof(Graph));
    G->V = V;
    G->E = 0;
    G->adjList = (Node **) malloc(sizeof(Node *) * V);
    for (int i = 0; i < V; i++) {
        G->adjList[i] = NULL;
    }
    return G;
}

// 添加边
void addEdge(Graph *G, int u, int v, int w) {
    Node *newNode = (Node *) malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->weight = w;
    newNode->next = G->adjList[u];
    G->adjList[u] = newNode;
    G->E++;
}

// 打印最短路径
void printPath(int *parent, int v) {
    if (parent[v] == -1) {
        printf("%d ", v);
        return;
    }
    printPath(parent, parent[v]);
    printf("%d ", v);
}

// Dijkstra算法
void dijkstra(Graph *G, int s) {
    int dist[MAX_VERTEX];  // 记录源点到各点的最短距离
    int parent[MAX_VERTEX];  // 记录最短路径中各点的父结点
    int visited[MAX_VERTEX] = {0};  // 记录各点是否已访问
    for (int i = 0; i < G->V; i++) {
        dist[i] = INF;
        parent[i] = -1;
    }
    dist[s] = 0;
    for (int i = 0; i < G->V - 1; i++) {
        int u = -1;
        for (int j = 0; j < G->V; j++) {
            if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
                u = j;
            }
        }
        visited[u] = 1;
        Node *temp = G->adjList[u];
        while (temp != NULL) {
            int v = temp->vertex;
            int w = temp->weight;
            if (!visited[v] && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                parent[v] = u;
            }
            temp = temp->next;
        }
    }
    // 打印结果
    for (int i = 0; i < G->V; i++) {
        if (i != s) {
            printf("%d -> %d: ", s, i);
            if (dist[i] == INF) {
                printf("No path\n");
            } else {
                printPath(parent, i);
                printf("(distance = %d)\n", dist[i]);
            }
        }
    }
}

int main() {
    int V = 5;
    Graph *G = initGraph(V);
    addEdge(G, 0, 1, 10);
    addEdge(G, 0, 4, 5);
    addEdge(G, 1, 2, 1);
    addEdge(G, 1, 4, 2);
    addEdge(G, 2, 3, 4);
    addEdge(G, 3, 2, 6);
    addEdge(G, 3, 0, 7);
    addEdge(G, 4, 1, 3);
    addEdge(G, 4, 2, 9);
    addEdge(G, 4, 3, 2);
    dijkstra(G, 0);
    return 0;
}

上面的代码中，`initGraph`函数用于初始化邻接表，`addEdge`函数用于添加边，`printPath`函数用于打印最短路径，`dijkstra`函数用于实现Dijkstra算法。在`main`函数中，我们创建了一个有向图，并调用`dijkstra`函数求出从源点0到其余各顶点的最短路径。