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

好的，下面是使用 C 语言实现 Dijkstra 算法的代码，假设图的邻接表存储在结构体数组 adjacency_list 中：

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

// 定义图的邻接表结构体
struct Edge {
    int dst;
    int weight;
    struct Edge* next;
};

struct Graph {
    int num_vertices;
    struct Edge** adjacency_list;
};

// 创建图的邻接表
struct Graph* create_graph(int num_vertices) {
    struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
    graph->num_vertices = num_vertices;
    graph->adjacency_list = (struct Edge**) malloc(num_vertices * sizeof(struct Edge*));
    for (int i = 0; i < num_vertices; i++) {
        graph->adjacency_list[i] = NULL;
    }
    return graph;
}

// 添加边到图的邻接表
void add_edge(struct Graph* graph, int src, int dst, int weight) {
    struct Edge* edge = (struct Edge*) malloc(sizeof(struct Edge));
    edge->dst = dst;
    edge->weight = weight;
    edge->next = graph->adjacency_list[src];
    graph->adjacency_list[src] = edge;
}

// Dijkstra 算法
void dijkstra(struct Graph* graph, int source, int* dist) {
    // 初始化
    int n = graph->num_vertices;
    for (int i = 0; i < n; i++) {
        dist[i] = INT_MAX;
    }
    dist[source] = 0;
    bool visited[n];
    for (int i = 0; i < n; i++) {
        visited[i] = false;
    }
    
    // 堆优化
    struct HeapNode {
        int dist;
        int u;
    };
    struct HeapNode heap[n];
    int heap_size = 0;
    bool in_heap[n];
    for (int i = 0; i < n; i++) {
        in_heap[i] = false;
    }
    
    // 将源点加入堆
    heap[heap_size].dist = 0;
    heap[heap_size].u = source;
    heap_size++;
    in_heap[source] = true;
    
    // 循环直到堆为空
    while (heap_size > 0) {
        // 从堆中弹出距离源点最近的点
        int u = heap[0].u;
        visited[u] = true;
        heap_size--;
        if (heap_size > 0) {
            heap[0] = heap[heap_size];
        }
        in_heap[u] = false;
        
        // 更新 u 的每一个邻居的 dist 值
        struct Edge* edge = graph->adjacency_list[u];
        while (edge != NULL) {
            int v = edge->dst;
            int w = edge->weight;
            if (!visited[v] && dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                // 将 v 加入堆
                if (!in_heap[v]) {
                    heap[heap_size].dist = dist[v];
                    heap[heap_size].u = v;
                    heap_size++;
                    in_heap[v] = true;
                } else {
                    // 如果 v 已经在堆中，更新堆中 v 的 dist 值
                    for (int i = 0; i < heap_size; i++) {
                        if (heap[i].u == v) {
                            heap[i].dist = dist[v];
                            break;
                        }
                    }
                }
                // 调整堆
                int i = heap_size - 1;
                while (i > 0) {
                    int parent = (i - 1) / 2;
                    if (heap[parent].dist <= heap[i].dist) {
                        break;
                    }
                    struct HeapNode tmp = heap[parent];
                    heap[parent] = heap[i];
                    heap[i] = tmp;
                    i = parent;
                }
            }
            edge = edge->next;
        }
    }
}

// 测试
int main() {
    struct Graph* graph = create_graph(5);
    add_edge(graph, 0, 1, 10);
    add_edge(graph, 0, 3, 5);
    add_edge(graph, 1, 2, 1);
    add_edge(graph, 1, 3, 2);
    add_edge(graph, 2, 4, 4);
    add_edge(graph, 3, 1, 3);
    add_edge(graph, 3, 2, 9);
    add_edge(graph, 3, 4, 2);
    add_edge(graph, 4, 0, 7);
    add_edge(graph, 4, 2, 6);
    int dist[5];
    dijkstra(graph, 0, dist);
    for (int i = 0; i < 5; i++) {
        printf("dist[%d] = %d\n", i, dist[i]);
    }
    return 0;
}

其中，堆优化使用了一个结构体数组 heap 和一个布尔数组 in_heap，heap 用于存储堆中的元素，in_heap 用于判断一个点是否已经在堆中。时间复杂度为 O(ElogV)，其中 E 表示边的数量，V 表示点的数量。