用堆排序优化邻接表存储的Dijkstra算法的C语言代码

以下是用堆排序优化邻接表存储的Dijkstra算法的C语言代码：

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

#define MAX_VERTEX_NUM 10000
#define INF INT_MAX

typedef struct EdgeNode {
    int adjvex;         // 邻接点编号
    int weight;         // 权值
    struct EdgeNode *next;  // 下一个邻接点
} EdgeNode;

typedef struct VertexNode {
    int data;           // 顶点编号
    EdgeNode *firstEdge;    // 第一个邻接点
} VertexNode;

typedef struct Graph {
    int vexnum, arcnum;     // 顶点数，边数
    VertexNode vertex[MAX_VERTEX_NUM];  // 顶点数组
} Graph;

typedef struct HeapNode {
    int vex;            // 顶点编号
    int dist;           // 最短路径长度
} HeapNode;

typedef struct Heap {
    int size;           // 堆大小
    HeapNode elem[MAX_VERTEX_NUM];      // 堆数组
} Heap;

void createGraph(Graph *G) {
    scanf("%d%d", &G->vexnum, &G->arcnum);
    for (int i = 1; i <= G->vexnum; i++) {
        G->vertex[i].data = i;
        G->vertex[i].firstEdge = NULL;
    }
    for (int i = 1; i <= G->arcnum; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        EdgeNode *e = (EdgeNode *) malloc(sizeof(EdgeNode));
        e->adjvex = v;
        e->weight = w;
        e->next = G->vertex[u].firstEdge;
        G->vertex[u].firstEdge = e;
    }
}

void initDist(int dist[], int v, int start) {
    for (int i = 1; i <= v; i++)
        dist[i] = INF;
    dist[start] = 0;
}

void initHeap(Heap *H, int dist[], int v, int start) {
    H->size = 0;
    for (int i = 1; i <= v; i++) {
        if (i != start) {
            H->elem[++H->size].vex = i;
            H->elem[H->size].dist = dist[i];
        }
    }
}

void swap(HeapNode *a, HeapNode *b) {
    HeapNode tmp = *a;
    *a = *b;
    *b = tmp;
}

void siftDown(Heap *H, int i) {
    int flag = 0;
    while (i * 2 <= H->size && !flag) {
        int minChild;
        if (i * 2 == H->size || H->elem[i * 2].dist < H->elem[i * 2 + 1].dist)
            minChild = i * 2;
        else
            minChild = i * 2 + 1;
        if (H->elem[i].dist > H->elem[minChild].dist) {
            swap(&H->elem[i], &H->elem[minChild]);
            i = minChild;
        } else
            flag = 1;
    }
}

void siftUp(Heap *H, int i) {
    int flag = 0;
    while (i > 1 && !flag) {
        if (H->elem[i].dist < H->elem[i / 2].dist) {
            swap(&H->elem[i], &H->elem[i / 2]);
            i /= 2;
        } else
            flag = 1;
    }
}

void insert(Heap *H, int vex, int dist[]) {
    H->elem[++H->size].vex = vex;
    H->elem[H->size].dist = dist[vex];
    siftUp(H, H->size);
}

int deleteMin(Heap *H, int dist[]) {
    int minVex = H->elem[1].vex;
    H->elem[1] = H->elem[H->size--];
    siftDown(H, 1);
    return minVex;
}

void dijkstra(Graph *G, int dist[], int start) {
    Heap H;
    EdgeNode *e;
    initDist(dist, G->vexnum, start);
    initHeap(&H, dist, G->vexnum, start);
    while (H.size > 0) {
        int u = deleteMin(&H, dist);
        e = G->vertex[u].firstEdge;
        while (e) {
            int v = e->adjvex;
            if (dist[v] > dist[u] + e->weight) {
                dist[v] = dist[u] + e->weight;
                for (int i = 1; i <= H.size; i++) {
                    if (H.elem[i].vex == v) {
                        H.elem[i].dist = dist[v];
                        siftUp(&H, i);
                        break;
                    }
                }
            }
            e = e->next;
        }
    }
}

int main() {
    Graph G;
    createGraph(&G);
    int dist[MAX_VERTEX_NUM];
    dijkstra(&G, dist, 1);
    for (int i = 1; i <= G.vexnum; i++)
        printf("%d ", dist[i]);
    return 0;
}

其中，`Heap`结构体表示堆，`HeapNode`结构体表示堆中的元素，`createGraph()`函数创建邻接表存储的图，`initDist()`函数初始化距离数组，`initHeap()`函数初始化堆，`swap()`函数交换两个元素的值，`siftDown()`函数下滤操作，`siftUp()`函数上滤操作，`insert()`函数向堆中插入一个元素，`deleteMin()`函数删除堆中的最小元素，`dijkstra()`函数实现Dijkstra算法。