用迪杰斯特拉算法求一个点到其他点的最短路径，用堆排序优化，图用邻接多重表储存，用C语言代码写一个程序

好的，下面是C语言代码实现：

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

// 邻接多重表的边结构体
typedef struct Edge {
    int vertex1;
    int vertex2;
    int weight;
    struct Edge *next1;
    struct Edge *next2;
} Edge;

// 邻接多重表的顶点结构体
typedef struct Vertex {
    int data;
    Edge *first_edge;
} Vertex;

// 堆结构体
typedef struct Heap {
    int *data;
    int size;
    int capacity;
} Heap;

// 初始化堆
Heap *init_heap(int capacity) {
    Heap *heap = (Heap *)malloc(sizeof(Heap));
    heap->data = (int *)malloc(sizeof(int) * (capacity + 1));
    heap->size = 0;
    heap->capacity = capacity;
    return heap;
}

// 插入元素到堆中
void insert_heap(Heap *heap, int element) {
    if (heap->size == heap->capacity) {
        return;
    }
    heap->data[++heap->size] = element;
    int i = heap->size;
    while (i > 1 && heap->data[i] < heap->data[i / 2]) {
        int temp = heap->data[i];
        heap->data[i] = heap->data[i / 2];
        heap->data[i / 2] = temp;
        i /= 2;
    }
}

// 弹出堆顶元素
int pop_heap(Heap *heap) {
    if (heap->size == 0) {
        return -1;
    }
    int ret = heap->data[1];
    heap->data[1] = heap->data[heap->size--];
    int i = 1, j = 2;
    while (j <= heap->size) {
        if (j + 1 <= heap->size && heap->data[j + 1] < heap->data[j]) {
            j = j + 1;
        }
        if (heap->data[i] > heap->data[j]) {
            int temp = heap->data[i];
            heap->data[i] = heap->data[j];
            heap->data[j] = temp;
            i = j;
            j = i * 2;
        } else {
            break;
        }
    }
    return ret;
}

// 判断堆是否为空
int is_empty_heap(Heap *heap) {
    return heap->size == 0;
}

// 释放堆内存
void free_heap(Heap *heap) {
    free(heap->data);
    free(heap);
}

// 初始化邻接多重表
void init_graph(Vertex *graph, int n) {
    for (int i = 0; i < n; i++) {
        graph[i].data = i + 1;
        graph[i].first_edge = NULL;
    }
}

// 添加边到邻接多重表中
void add_edge(Vertex *graph, int vertex1, int vertex2, int weight) {
    Edge *edge = (Edge *)malloc(sizeof(Edge));
    edge->vertex1 = vertex1;
    edge->vertex2 = vertex2;
    edge->weight = weight;
    edge->next1 = graph[vertex1 - 1].first_edge;
    edge->next2 = graph[vertex2 - 1].first_edge;
    graph[vertex1 - 1].first_edge = edge;
    graph[vertex2 - 1].first_edge = edge;
}

// 释放邻接多重表内存
void free_graph(Vertex *graph, int n) {
    for (int i = 0; i < n; i++) {
        Edge *edge = graph[i].first_edge;
        while (edge != NULL) {
            Edge *temp = edge;
            edge = edge->next1 == edge ? NULL : edge->next1;
            free(temp);
        }
    }
}

// 迪杰斯特拉算法求解最短路径
void dijkstra(Vertex *graph, int n, int start, int *dist) {
    // 初始化距离数组
    for (int i = 0; i < n; i++) {
        dist[i] = INT_MAX;
    }
    dist[start - 1] = 0;
    // 初始化堆
    Heap *heap = init_heap(n);
    insert_heap(heap, start);
    // 迭代更新距离数组
    while (!is_empty_heap(heap)) {
        int vertex = pop_heap(heap);
        Edge *edge = graph[vertex - 1].first_edge;
        while (edge != NULL) {
            int next_vertex = edge->vertex1 == vertex ? edge->vertex2 : edge->vertex1;
            if (dist[next_vertex - 1] > dist[vertex - 1] + edge->weight) {
                dist[next_vertex - 1] = dist[vertex - 1] + edge->weight;
                insert_heap(heap, next_vertex);
            }
            edge = edge->next1 == edge ? NULL : (edge->next1->vertex1 == vertex ? edge->next1->next2 : edge->next1);
        }
    }
    // 释放堆内存
    free_heap(heap);
}

int main() {
    int n = 5;
    Vertex *graph = (Vertex *)malloc(sizeof(Vertex) * n);
    init_graph(graph, n);

    add_edge(graph, 1, 2, 10);
    add_edge(graph, 1, 4, 30);
    add_edge(graph, 1, 5, 100);
    add_edge(graph, 2, 3, 50);
    add_edge(graph, 3, 5, 10);
    add_edge(graph, 4, 3, 20);
    add_edge(graph, 4, 5, 60);

    int start = 1;
    int *dist = (int *)malloc(sizeof(int) * n);
    dijkstra(graph, n, start, dist);

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

    free(dist);
    free_graph(graph, n);
    free(graph);
    return 0;
}

这个程序实现了一个邻接多重表的图数据结构，使用了迪杰斯特拉算法求解最短路径，并用堆排序优化了算法。程序输出了从第一个点出发到其他点的最短路径。