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

单源最短路径问题可以使用 Dijkstra 算法来解决，而优先队列是 Dijkstra 算法的重要组成部分，可以用来存储待处理的节点。

下面是使用 C 语言实现优先队列的单源最短路径问题的代码：

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

#define MAX_VERTICES 100
#define INF INT_MAX

typedef struct {
    int vertex;
    int weight;
} edge;

typedef struct {
    edge* edges[MAX_VERTICES];
    int size[MAX_VERTICES];
} graph;

typedef struct {
    int priority;
    int vertex;
} node;

typedef struct {
    node* heap[MAX_VERTICES];
    int size;
} priority_queue;

void init_graph(graph* g, int n) {
    for (int i = 0; i < n; i++) {
        g->size[i] = 0;
    }
}

void add_edge(graph* g, int u, int v, int w) {
    edge* e = (edge*)malloc(sizeof(edge));
    e->vertex = v;
    e->weight = w;
    g->edges[u][g->size[u]] = e;
    g->size[u]++;
}

void init_priority_queue(priority_queue* q) {
    q->size = 0;
}

void push(priority_queue* q, int priority, int vertex) {
    node* n = (node*)malloc(sizeof(node));
    n->priority = priority;
    n->vertex = vertex;
    q->heap[q->size] = n;
    q->size++;

    int i = q->size - 1;
    while (i > 0 && q->heap[i]->priority < q->heap[(i - 1) / 2]->priority) {
        node* temp = q->heap[i];
        q->heap[i] = q->heap[(i - 1) / 2];
        q->heap[(i - 1) / 2] = temp;
        i = (i - 1) / 2;
    }
}

node* pop(priority_queue* q) {
    node* result = q->heap[0];
    q->size--;
    q->heap[0] = q->heap[q->size];

    int i = 0;
    while (2 * i + 1 < q->size) {
        int left_child = 2 * i + 1;
        int right_child = 2 * i + 2;
        int min_child = left_child;

        if (right_child < q->size && q->heap[right_child]->priority < q->heap[min_child]->priority) {
            min_child = right_child;
        }

        if (q->heap[i]->priority <= q->heap[min_child]->priority) {
            break;
        }

        node* temp = q->heap[i];
        q->heap[i] = q->heap[min_child];
        q->heap[min_child] = temp;
        i = min_child;
    }

    return result;
}

void dijkstra(graph* g, int start, int* distance) {
    priority_queue q;
    init_priority_queue(&q);

    for (int i = 0; i < MAX_VERTICES; i++) {
        distance[i] = INF;
    }

    distance[start] = 0;
    push(&q, 0, start);

    while (q.size > 0) {
        node* n = pop(&q);
        int u = n->vertex;
        free(n);

        for (int i = 0; i < g->size[u]; i++) {
            edge* e = g->edges[u][i];
            int v = e->vertex;
            int w = e->weight;

            if (distance[u] + w < distance[v]) {
                distance[v] = distance[u] + w;
                push(&q, distance[v], v);
            }
        }
    }
}

int main() {
    graph g;
    init_graph(&g, MAX_VERTICES);

    add_edge(&g, 0, 1, 2);
    add_edge(&g, 0, 2, 5);
    add_edge(&g, 1, 2, 2);
    add_edge(&g, 1, 3, 3);
    add_edge(&g, 2, 1, 1);
    add_edge(&g, 2, 3, 1);
    add_edge(&g, 2, 4, 3);
    add_edge(&g, 3, 4, 1);
    add_edge(&g, 4, 3, 1);

    int distance[MAX_VERTICES];
    dijkstra(&g, 0, distance);

    for (int i = 0; i < MAX_VERTICES; i++) {
        printf("distance from 0 to %d: %d\n", i, distance[i]);
    }

    return 0;
}

在这个代码中，使用了一个 `graph` 结构体来表示图，其中 `size` 数组存储每个节点的出度，`edges` 数组存储每条边的终点和权重。

使用一个 `priority_queue` 结构体来表示优先队列，其中 `size` 表示队列的大小，`heap` 数组存储每个节点的优先级和值。

使用 `push` 函数向优先队列中添加一个节点，使用 `pop` 函数从优先队列中弹出一个节点。

最后，使用 `dijkstra` 函数来计算从起始节点到其他节点的最短路径，使用 `distance` 数组来存储结果。