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

优先队列可以用于实现单源最短路径问题，其中最常见的算法是Dijkstra算法。下面是使用C语言实现Dijkstra算法的示例代码：

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

#define MAX_VERTICES 1000

// 用邻接矩阵表示图
int graph[MAX_VERTICES][MAX_VERTICES];
int dist[MAX_VERTICES]; // 存储每个节点的最短路径
int visited[MAX_VERTICES]; // 标记每个节点是否已经访问过
int vertex_count; // 节点数量

// 创建一个新的优先队列
struct PriorityQueue {
    int* nodes;
    int count;
};

// 初始化队列
void init_queue(struct PriorityQueue* q) {
    q->nodes = (int*) malloc(vertex_count * sizeof(int));
    q->count = 0;
}

// 将节点插入队列
void enqueue(struct PriorityQueue* q, int value) {
    int i;
    for (i = 0; i < q->count; i++) {
        if (dist[q->nodes[i]] > dist[value]) {
            // 插入到当前节点之前
            int j;
            for (j = q->count; j > i; j--) {
                q->nodes[j] = q->nodes[j - 1];
            }
            q->nodes[i] = value;
            q->count++;
            return;
        }
    }
    q->nodes[q->count++] = value;
}

// 从队列中取出最小的节点
int dequeue(struct PriorityQueue* q) {
    return q->nodes[--q->count];
}

// 判断队列是否为空
int is_empty(struct PriorityQueue* q) {
    return q->count == 0;
}

// Dijkstra算法
void dijkstra(int start) {
    int i;
    for (i = 0; i < vertex_count; i++) {
        dist[i] = INT_MAX; // 初始化所有节点的距离为无穷大
        visited[i] = 0; // 所有节点都未被访问过
    }
    dist[start] = 0; // 起点到自己的距离为0
    struct PriorityQueue q;
    init_queue(&q);
    enqueue(&q, start); // 将起点插入队列
    while (!is_empty(&q)) {
        int node = dequeue(&q); // 取出队列中最小的节点
        if (visited[node]) {
            continue; // 如果已经访问过，就继续下一个节点
        }
        visited[node] = 1; // 将当前节点标记为已访问
        for (i = 0; i < vertex_count; i++) {
            if (graph[node][i] != 0) { // 如果有相邻的节点
                int new_dist = dist[node] + graph[node][i];
                if (new_dist < dist[i]) { // 如果新路径比原路径更短
                    dist[i] = new_dist; // 更新节点的最短路径
                    enqueue(&q, i); // 将节点插入队列
                }
            }
        }
    }
}

int main() {
    int i, j;
    scanf("%d", &vertex_count);
    for (i = 0; i < vertex_count; i++) {
        for (j = 0; j < vertex_count; j++) {
            scanf("%d", &graph[i][j]); // 输入邻接矩阵
        }
    }
    dijkstra(0); // 以0号节点为起点
    for (i = 0; i < vertex_count; i++) {
        printf("%d ", dist[i]); // 输出每个节点的最短路径
    }
    return 0;
}

这段代码使用优先队列来实现Dijkstra算法，使用邻接矩阵来表示图。输入格式为：

节点数
邻接矩阵

其中邻接矩阵是一个N*N的矩阵，第i行第j列的元素表示从第i个节点到第j个节点的边权值。如果两个节点之间没有边，则对应的元素为0。输出每个节点的最短路径。