C语言优先队列的单源最短路径问题

在单源最短路径问题中，我们需要找到从源节点到所有其他节点的最短路径。常见的算法有Dijkstra算法和Bellman-Ford算法，其中Dijkstra算法适用于正权重边的图，而Bellman-Ford算法可以处理负权重边的图。

使用优先队列可以优化Dijkstra算法的时间复杂度，使其达到O(E*logV)，其中E为边数，V为顶点数。具体实现方式是用一个数组dist[]记录源节点到每个节点的距离，将源节点入队，然后不断从队列中取出离源节点最近的节点u，并更新与u相邻的节点v的距离，如果新的距离比原来的距离小，则将v加入队列。

以下是C语言实现Dijkstra算法的代码：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_VERTICES 1000
#define INF 1000000000

typedef struct {
    int v;  // 目标节点
    int w;  // 边权重
} Edge;

typedef struct {
    Edge* edges[MAX_VERTICES];  // 邻接表
    int degree[MAX_VERTICES];   // 出度
    int num_vertices;           // 顶点数
} Graph;

Graph* create_graph(int n) {
    Graph* g = (Graph*)malloc(sizeof(Graph));
    g->num_vertices = n;
    for (int i = 0; i < n; i++) {
        g->edges[i] = NULL;
        g->degree[i] = 0;
    }
    return g;
}

void add_edge(Graph* g, int u, int v, int w) {
    Edge* e = (Edge*)malloc(sizeof(Edge));
    e->v = v;
    e->w = w;
    e->next = g->edges[u];
    g->edges[u] = e;
    g->degree[u]++;
}

void dijkstra(Graph* g, int s, int* dist) {
    bool visited[MAX_VERTICES] = {false};
    for (int i = 0; i < g->num_vertices; i++) {
        dist[i] = INF;
    }
    dist[s] = 0;

    typedef struct {
        int v;
        int d;
    } Node;
    #define MAX_NODES 10000
    Node heap[MAX_NODES];
    int heap_size = 0;

    heap[heap_size++] = (Node){s, 0};

    while (heap_size > 0) {
        Node x = heap[0];
        heap[0] = heap[--heap_size];
        int i = 0;
        while (i * 2 + 1 < heap_size) {
            int a = i * 2 + 1, b = i * 2 + 2;
            if (b < heap_size && heap[b].d < heap[a].d) {
                a = b;
            }
            if (heap[a].d >= heap[i].d) {
                break;
            }
            Node t = heap[i];
            heap[i] = heap[a];
            heap[a] = t;
            i = a;
        }

        if (visited[x.v]) {
            continue;
        }
        visited[x.v] = true;

        for (Edge* e = g->edges[x.v]; e != NULL; e = e->next) {
            int v = e->v, w = e->w;
            if (dist[v] > dist[x.v] + w) {
                dist[v] = dist[x.v] + w;
                heap[heap_size++] = (Node){v, dist[v]};
                int i = heap_size - 1;
                while (i > 0) {
                    int p = (i - 1) / 2;
                    if (heap[p].d <= heap[i].d) {
                        break;
                    }
                    Node t = heap[p];
                    heap[p] = heap[i];
                    heap[i] = t;
                    i = p;
                }
            }
        }
    }
}

int main() {
    Graph* g = create_graph(4);
    add_edge(g, 0, 1, 2);
    add_edge(g, 0, 2, 3);
    add_edge(g, 1, 2, 1);
    add_edge(g, 1, 3, 4);
    add_edge(g, 2, 3, 1);

    int dist[MAX_VERTICES];
    dijkstra(g, 0, dist);

    for (int i = 0; i < g->num_vertices; i++) {
        printf("%d ", dist[i]);
    }
    printf("\n");

    return 0;
}

上面的代码中，我们使用了一个最小堆来维护离源节点最近的节点。为了方便，我们使用了C语言中的宏定义来模拟面向对象的结构体和方法。这份代码可以处理最多1000个顶点和10000条边的图，如果需要处理更大的图，可以根据具体情况调整MAX_VERTICES和MAX_NODES的大小。