dijkstra算法堆优化c++

当然可以，以下是一个使用堆优化的 Dijkstra 算法的 C 代码示例：

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

#define MAX_VERTICES 10000
#define INF INT_MAX

typedef struct {
    int v;
    int w;
} Edge;

typedef struct {
    Edge* edges[MAX_VERTICES];
    int edge_count[MAX_VERTICES];
    int vertex_count;
} Graph;

typedef struct {
    int* heap;
    int* indices;
    int* dist;
    int size;
} Heap;

Graph* create_graph(int vertex_count) {
    Graph* graph = (Graph*) malloc(sizeof(Graph));
    graph->vertex_count = vertex_count;
    for (int i = 0; i < vertex_count; i++) {
        graph->edges[i] = (Edge*) malloc(sizeof(Edge) * vertex_count);
        graph->edge_count[i] = 0;
    }
    return graph;
}

void add_edge(Graph* graph, int u, int v, int w) {
    Edge edge = {v, w};
    graph->edges[u][graph->edge_count[u]++] = edge;
}

Heap* create_heap(int size) {
    Heap* heap = (Heap*) malloc(sizeof(Heap));
    heap->heap = (int*) malloc(sizeof(int) * size);
    heap->indices = (int*) malloc(sizeof(int) * size);
    heap->dist = (int*) malloc(sizeof(int) * size);
    heap->size = 0;
    return heap;
}

void heap_swap(Heap* heap, int i, int j) {
    int temp = heap->heap[i];
    heap->heap[i] = heap->heap[j];
    heap->heap[j] = temp;
    heap->indices[heap->heap[i]] = i;
    heap->indices[heap->heap[j]] = j;
}

void heap_push(Heap* heap, int v, int dist) {
    heap->heap[heap->size] = v;
    heap->indices[v] = heap->size;
    heap->dist[v] = dist;
    int i = heap->size++;
    while (i > 0) {
        int p = (i - 1) / 2;
        if (heap->dist[heap->heap[i]] < heap->dist[heap->heap[p]]) {
            heap_swap(heap, i, p);
            i = p;
        } else {
            break;
        }
    }
}

int heap_pop(Heap* heap) {
    int v = heap->heap[0];
    heap->indices[v] = -1;
    heap->heap[0] = heap->heap[--heap->size];
    heap->indices[heap->heap[0]] = 0;
    int i = 0;
    while (i * 2 + 1 < heap->size) {
        int l = i * 2 + 1;
        int r = i * 2 + 2;
        int j = l;
        if (r < heap->size && heap->dist[heap->heap[r]] < heap->dist[heap->heap[l]]) {
            j = r;
        }
        if (heap->dist[heap->heap[j]] < heap->dist[heap->heap[i]]) {
            heap_swap(heap, i, j);
            i = j;
        } else {
            break;
        }
    }
    return v;
}

void dijkstra(Graph* graph, int s, int* dist) {
    Heap* heap = create_heap(graph->vertex_count);
    for (int i = 0; i < graph->vertex_count; i++) {
        dist[i] = INF;
    }
    dist[s] = 0;
    heap_push(heap, s, 0);
    while (heap->size > 0) {
        int u = heap_pop(heap);
        for (int i = 0; i < graph->edge_count[u]; i++) {
            int v = graph->edges[u][i].v;
            int w = graph->edges[u][i].w;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (heap->indices[v] >= 0) {
                    heap_push(heap, v, dist[v]);
                } else {
                    heap_push(heap, v, dist[v]);
                }
            }
        }
    }
}

int main() {
    int n, m, s;
    scanf("%d%d%d", &n, &m, &s);
    Graph* graph = create_graph(n);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add_edge(graph, u - 1, v - 1, w);
    }
    int dist[MAX_VERTICES];
    dijkstra(graph, s - 1, dist);
    for (int i = 0; i < n; i++) {
        if (dist[i] == INF) {
            printf("INF\n");
        } else {
            printf("%d\n", dist[i]);
        }
    }
    return 0;
}

希望这个代码能够帮助你理解 Dijkstra 算法的堆优化实现。