邻接表解决单源最短路径问题C语言代码

在C语言中，使用Dijkstra算法来解决单源最短路径问题时，邻接表是一个常见的数据结构选择。下面是一个简化的Dijkstra算法实现，假设我们有一个已排序的数组来表示距离：

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

#define V 9 // 图的顶点数
#define INF INT_MAX

typedef struct {
    int destination; // 目标顶点
    int distance;     // 到达目标的距离
} Node;

// 使用优先队列（堆）来存放节点
struct pqNode {
    Node node;
    int priority;
};

void dijkstra(Node* adj_list[], int src) {
    int dist[V] = {INF};
    dist[src] = 0;
    Node pq[V]; // 优先队列
    int i, u, v, minDistance;

    for (i = 0; i < V; i++) {
        pq[i].node.destination = i;
        pq[i].priority = dist[i];
        pq[i].node.distance = dist[i];
    }

    while (!isEmpty(pq)) {
        minDistance = pq[0].priority;
        u = pq[0].node.destination;
        removeMin(pq);

        // 更新所有从u可达的顶点的最短距离
        for (v = first(adj_list[u]); v != NULL; v = next(adj_list[u], v)) {
            if (dist[v->destination] > dist[u] + v->distance) {
                dist[v->destination] = dist[u] + v->distance;
                updatePriority(&pq[v->destination]);
            }
        }
    }

    printf("Shortest distances from source %d are:\n", src);
    for (i = 0; i < V; i++)
        printf("%d -> %d = %d\n", src, i, dist[i]);
}

int main() {
    // 请在这里填写你的邻接列表结构和初始化方法
    // adj_list[i] should be a linked list with nodes having destination and distance fields
    dijkstra(adj_list, 0); // 源顶点0
    return 0;
}

请注意，这里的`adj_list[]`应该是一个二维数组或类似的数据结构，其中`adj_list[i]`代表顶点`i`的所有邻居及其边的权重。你需要根据实际情况调整这个结构，并提供正确的初始化方法。同时，这里假设了优先队列（堆）的相关函数如`isEmpty()`、`removeMin()`和`updatePriority()`已经实现。