dijkstra求单源最短路径c语言

以下是 Dijkstra 算法求解单源最短路径的 C 语言实现：

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

// 定义无穷大
#define INF INT_MAX

// 定义顶点数量和边数量的最大值
#define MAXV 1000
#define MAXE 100000

// 定义边结构体
typedef struct {
    int to;     // 目标顶点
    int weight; // 权重
} Edge;

// 定义图结构体
typedef struct {
    Edge edges[MAXE];   // 边列表
    int head[MAXV];     // 每个顶点的第一条边的编号
    int next[MAXE];     // 下一条边的编号
    int ecnt;           // 边数
    int n;              // 顶点数
} Graph;

// 初始化图
void graph_init(Graph* g, int n) {
    g->n = n;
    g->ecnt = 0;
    for (int i = 0; i < n; i++) {
        g->head[i] = -1;
    }
}

// 添加边
void graph_add_edge(Graph* g, int u, int v, int w) {
    g->edges[g->ecnt].to = v;
    g->edges[g->ecnt].weight = w;
    g->next[g->ecnt] = g->head[u];
    g->head[u] = g->ecnt;
    g->ecnt++;
}

// Dijkstra 算法
void dijkstra(Graph* g, int s, int* dist) {
    // 初始化距离数组
    for (int i = 0; i < g->n; i++) {
        dist[i] = INF;
    }
    dist[s] = 0;

    // 构建最小堆
    int heap[MAXV], hcnt = 0;
    int pos[MAXV];
    for (int i = 0; i < g->n; i++) {
        heap[hcnt] = i;
        pos[i] = hcnt;
        hcnt++;
    }

    // 最小堆的上浮操作
    void heap_up(int i) {
        while (i > 0) {
            int p = (i - 1) / 2;
            if (dist[heap[p]] <= dist[heap[i]]) break;
            int t = heap[p];
            heap[p] = heap[i];
            heap[i] = t;
            pos[heap[p]] = p;
            pos[heap[i]] = i;
            i = p;
        }
    }

    // 最小堆的下沉操作
    void heap_down(int i) {
        while (2 * i + 1 < hcnt) {
            int l = 2 * i + 1, r = 2 * i + 2;
            int p = i;
            if (dist[heap[l]] < dist[heap[p]]) p = l;
            if (r < hcnt && dist[heap[r]] < dist[heap[p]]) p = r;
            if (p == i) break;
            int t = heap[p];
            heap[p] = heap[i];
            heap[i] = t;
            pos[heap[p]] = p;
            pos[heap[i]] = i;
            i = p;
        }
    }

    // 从最小堆中取出距离最小的顶点
    int heap_pop() {
        int t = heap[0];
        heap[0] = heap[hcnt - 1];
        pos[heap[0]] = 0;
        hcnt--;
        heap_down(0);
        return t;
    }

    // 逐步更新距离数组
    while (hcnt > 0) {
        int u = heap_pop();
        for (int i = g->head[u]; i != -1; i = g->next[i]) {
            int v = g->edges[i].to;
            int w = g->edges[i].weight;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                heap_up(pos[v]);
            }
        }
    }
}

int main() {
    Graph g;
    graph_init(&g, 5);
    graph_add_edge(&g, 0, 1, 1);
    graph_add_edge(&g, 0, 2, 3);
    graph_add_edge(&g, 1, 2, 1);
    graph_add_edge(&g, 1, 3, 4);
    graph_add_edge(&g, 2, 4, 2);
    graph_add_edge(&g, 3, 4, 3);
    int dist[MAXV];
    dijkstra(&g, 0, dist);
    for (int i = 0; i < g.n; i++) {
        printf("dist[%d] = %d\n", i, dist[i]);
    }
    return 0;
}

上述代码实现了 Dijkstra 算法求解单源最短路径，使用了最小堆来实现优先级队列，从而提高了算法的效率。