Dijkstra算法C语言实现：从朴素到堆优化，图解与避坑指南

1. 为什么一个几十行的算法值得反复琢磨

很多人第一次接触图论最短路径，都是从Dijkstra开始的。课本上把它讲成一个贪心策略，伪代码不到二十行，看起来简单得不像话。但真到用C语言把它写出来、跑通、跑对、跑快，中间踩的坑远比想象中多。我见过太多人背得出"每次选距离最小的未访问节点"这句话，却在手写代码时被优先队列、松弛操作、无穷大溢出、有向无向这些细节卡住半天。

这篇内容就是围绕Dijkstra算法的C语言实现展开的。我会把整个实现过程拆开，从数据结构选型、核心循环设计，到完整可编译的代码、图解推演、常见bug排查，一步步讲清楚。目标读者是正在学图论的学生、准备算法面试的开发者，以及需要在工程项目里落地最短路径计算的工程师。哪怕你之前只写过Hello World级别的C程序，跟着走也能把这份代码跑起来。

先说清楚Dijkstra能解决什么问题：给定一个带权图和一个起点，求出起点到其余所有节点的最短路径长度。它的前提是边权非负，这一点非常关键，后面会专门讲为什么负权边会让它失效。它的典型应用场景包括地图导航的路径规划、网络路由的选路、游戏里NPC的寻路、物流调度的成本最小化等等。理解了它，你就拿到了图论算法的一把入门钥匙。

我下面给出的实现会包含两个版本：一个是适合初学者理解的邻接矩阵加朴素扫描版本，复杂度O(V²)；另一个是邻接表加二叉堆优化的版本，复杂度O((V+E)logV)。两个版本我都会给出完整代码和图解，你可以根据图的稠密程度来选择。

2. 算法核心思路与方案选型拆解

2.1 贪心策略到底在贪什么

Dijkstra的本质是一个贪心加动态规划的混合体。它维护一个距离数组dist[]，dist[i]表示从起点到节点i当前已知的最短距离。初始时起点距离为0，其余全部设为无穷大。然后每一轮，从"还没确定最终距离"的节点集合里，挑出dist值最小的那个节点u，把它标记为已确定，接着用u去"松弛"它的所有邻居：如果dist[u] + weight(u,v) < dist[v]，就更新dist[v]。

为什么这样做是对的？核心在于边权非负这个前提。当所有边权都大于等于0时，当前dist最小的那个未确定节点，它的距离不可能再通过其他未确定节点绕路变得更短——因为任何绕路都要加上非负的边权，只会更大。这个性质保证了贪心选择的正确性。一旦存在负权边，这个推理就崩了，所以Dijkstra对负权图无效，那种情况得用Bellman-Ford或者SPFA。

用生活化的类比：把节点想成城市，边权想成油费。你从家出发，每次总是先去"目前花费最少就能到达"的那个城市，因为去更远的城市再绕回来，油费只会更多不会更少。这个直觉就是Dijkstra的全部精髓。

2.2 邻接矩阵还是邻接表

选数据结构是写这个算法的第一个决策点，直接决定代码复杂度和运行效率。我整理了一张对比表，方便你按场景选：

结论很直接：节点数少（比如几百以内）或者图很稠密，用邻接矩阵，代码简单不容易错；节点数上千、边相对稀疏，用邻接表加堆优化，否则O(V²)在V=10000时就是一亿次操作，会明显卡顿。

2.3 朴素版和堆优化版的取舍

朴素版每轮用一次线性扫描找最小dist节点，这个扫描是O(V)，总共V轮，所以是O(V²)。堆优化版把"找最小"这件事交给优先队列，每次取出是O(logV)，每条边最多触发一次入堆，所以整体是O((V+E)logV)。

但这里有个很多人忽略的点：C语言标准库没有现成的优先队列。C++有priority_queue，Java有PriorityQueue，C什么都没有，你得自己手写一个二叉堆。这就是为什么很多C语言教程只讲朴素版——堆要自己造。我下面两个版本都给，堆优化版的堆我会写得尽量精简，方便你直接抄。

提示：不要一上来就追求堆优化。先用朴素版把逻辑跑通、结果验证正确，再换成堆优化做性能提升。顺序反了容易在堆的边界条件上浪费大量时间。

3. 朴素版完整实现与逐行图解

3.1 数据结构定义与初始化

先定义图。用邻接矩阵的话，一个二维数组就够了。我用INF表示无穷大，这里有个坑：不要用INT_MAX，因为松弛时dist[u] + graph[u][v]会整数溢出变成负数，导致错误更新。我一般取一个足够大的数，比如0x3f3f3f3f，它约等于10.6亿，两个相加也不会溢出int范围。

#include <stdio.h> #include <stdbool.h> #define MAXV 1000 #define INF 0x3f3f3f3f int graph[MAXV][MAXV]; // 邻接矩阵，graph[i][j]表示i到j的边权 int dist[MAXV]; // 起点到各点的最短距离 bool visited[MAXV]; // 是否已确定最短距离 int prev[MAXV]; // 记录前驱节点，用于还原路径 int V; // 节点数

初始化函数要做三件事：矩阵全部置INF（自己到自己置0）、dist全部置INF、visited全部置false。注意矩阵对角线graph[i][i]要设成0，否则自己到自己反而"不可达"。

void init_graph(int n) { V = n; for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { graph[i][j] = (i == j) ? 0 : INF; } } }

3.2 核心循环的每一步推演

主循环的逻辑是：重复V次，每次找一个未访问的、dist最小的节点u，标记访问，然后松弛u的所有邻居。找最小那一步如果找不到（dist仍是INF），说明剩下的节点都不可达，可以直接跳出。

void dijkstra(int start) { for (int i = 0; i < V; i++) { dist[i] = INF; visited[i] = false; prev[i] = -1; } dist[start] = 0; for (int round = 0; round < V; round++) { // 第一步：找未访问节点中dist最小的 int u = -1; int minDist = INF; for (int i = 0; i < V; i++) { if (!visited[i] && dist[i] < minDist) { minDist = dist[i]; u = i; } } if (u == -1) break; // 剩余节点都不可达 visited[u] = true; // 第二步：松弛u的所有邻居 for (int v = 0; v < V; v++) { if (!visited[v] && graph[u][v] != INF) { int newDist = dist[u] + graph[u][v]; if (newDist < dist[v]) { dist[v] = newDist; prev[v] = u; } } } } }

我用一个具体的小图走一遍，你就能看清每一步在干什么。假设有5个节点，边如下：0-1权10，0-2权3，2-1权4，1-3权2，2-3权8，3-4权7，2-4权20。

初始：dist = [0, INF, INF, INF, INF]，visited全false。

第一轮：找最小，u=0（dist=0）。松弛邻居1和2：dist[1]=10，dist[2]=3。此时dist = [0, 10, 3, INF, INF]。

第二轮：未访问中最小是节点2（dist=3），u=2。松弛邻居1、3、4：dist[1] = min(10, 3+4)=7，dist[3] = 3+8=11，dist[4] = 3+20=23。此时dist = [0, 7, 3, 11, 23]。

第三轮：未访问中最小是节点1（dist=7），u=1。松弛邻居3：dist[3] = min(11, 7+2)=9。dist = [0, 7, 3, 9, 23]。

第四轮：未访问中最小是节点3（dist=9），u=3。松弛邻居4：dist[4] = min(23, 9+7)=16。dist = [0, 7, 3, 9, 16]。

第五轮：只剩节点4，u=4，没有可松弛的邻居。结束。

最终起点0到各点最短距离是[0, 7, 3, 9, 16]。你可以手动验证一下，比如到节点1，直接走0-1是10，走0-2-1是3+4=7，确实更短，算法正确找到了。

3.3 路径还原的写法

很多时候你不仅要距离，还要具体走哪条路。这就是prev[]数组的用途。每次更新dist[v]时顺手记下prev[v]=u，最后从终点往回倒推即可。

void print_path(int start, int end) { if (dist[end] == INF) { printf("节点 %d 不可达\n", end); return; } int path[MAXV], len = 0; for (int cur = end; cur != -1; cur = prev[cur]) { path[len++] = cur; } printf("路径: "); for (int i = len - 1; i >= 0; i--) { printf("%d", path[i]); if (i > 0) printf(" -> "); } printf(" (总距离 %d)\n", dist[end]); }

注意：倒推时循环条件是cur != -1，因为起点的prev是-1。如果图里存在环或者prev被错误覆盖，这里可能死循环，所以初始化时务必把prev全部置-1。

4. 堆优化版：自己动手造一个优先队列

4.1 为什么C语言必须手写堆

前面说过，C标准库没有优先队列。有人想用qsort每轮排一次序，那是O(V²logV)，比朴素版还慢，纯属负优化。正确做法是用二叉最小堆，配合邻接表。堆里存的是(距离, 节点)这样的二元组，每次取堆顶就是当前最小距离。

这里有个经典技巧叫惰性删除：当一个节点的距离被更新后，旧的那条记录还留在堆里，我们不主动删它，而是在取出时判断——如果取出的距离大于当前dist[节点]，说明这是过期记录，直接丢弃。这样省去了在堆里查找和删除的麻烦，代码简单很多。

4.2 邻接表与堆的代码实现

先定义邻接表。用数组模拟链表，比指针好写也好调。

#define MAXE 200000 typedef struct { int to; int weight; int next; } Edge; Edge edges[MAXE]; int head[MAXV]; int edgeCnt = 0; void add_edge(int u, int v, int w) { edges[edgeCnt].to = v; edges[edgeCnt].weight = w; edges[edgeCnt].next = head[u]; head[u] = edgeCnt++; }

然后是堆。堆里每个元素是(dist, node)，我用两个平行数组或者一个结构体数组都行，这里用结构体更清晰。

typedef struct { int dist; int node; } HeapNode; HeapNode heap[MAXE]; int heapSize = 0; void heap_push(int d, int u) { int i = heapSize++; heap[i].dist = d; heap[i].node = u; // 上浮 while (i > 0) { int parent = (i - 1) / 2; if (heap[parent].dist <= heap[i].dist) break; HeapNode tmp = heap[parent]; heap[parent] = heap[i]; heap[i] = tmp; i = parent; } } HeapNode heap_pop() { HeapNode top = heap[0]; heap[0] = heap[--heapSize]; // 下沉 int i = 0; while (1) { int left = 2 * i + 1; int right = 2 * i + 2; int smallest = i; if (left < heapSize && heap[left].dist < heap[smallest].dist) smallest = left; if (right < heapSize && heap[right].dist < heap[smallest].dist) smallest = right; if (smallest == i) break; HeapNode tmp = heap[smallest]; heap[smallest] = heap[i]; heap[i] = tmp; i = smallest; } return top; }

堆的上浮和下沉是手写堆最容易写错的地方，尤其是下标计算。记住：父节点是(i-1)/2，左孩子是2i+1，右孩子是2i+2。这三个公式背下来，堆就不会写错。

4.3 堆优化主循环与惰性删除

有了堆和邻接表，主循环就清爽了。每次弹出堆顶，如果是过期记录就跳过，否则用它松弛邻居，更新成功就把新记录压入堆。

void dijkstra_heap(int start) { for (int i = 0; i < V; i++) { dist[i] = INF; prev[i] = -1; } dist[start] = 0; heapSize = 0; heap_push(0, start); while (heapSize > 0) { HeapNode cur = heap_pop(); int u = cur.node; int d = cur.dist; // 惰性删除：过期记录直接丢弃 if (d > dist[u]) continue; for (int e = head[u]; e != -1; e = edges[e].next) { int v = edges[e].to; int w = edges[e].weight; if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; prev[v] = u; heap_push(dist[v], v); } } } }

对比一下两个版本：朴素版没有visited数组也能跑（靠dist判断），但堆优化版不需要visited数组，因为惰性删除已经保证了每个节点只会被有效处理一次。这是很多人写堆优化时多此一举的地方。

提示：堆数组的大小要开到边数的量级，因为每条边最多触发一次入堆。开小了会数组越界，这个bug很隐蔽，可能在小数据下不报错，大数据下直接崩溃。

5. 常见问题与排查技巧实录

5.1 结果全错或部分错，先查这几个地方

Dijkstra写错，90%的问题集中在下面几个点。我整理成速查表，出问题时按顺序排查：

5.2 有向图和无向图的处理差异

这是新手最容易翻车的点。无向图的一条边等价于两条有向边，所以加边时要加两次：

// 无向图 add_edge(u, v, w); add_edge(v, u, w); // 有向图只加一次 add_edge(u, v, w);

邻接矩阵版本同理，无向图要graph[u][v] = graph[v][u] = w。我见过有人无向图只加了一条边，结果跑出来一堆不可达，debug半天才发现。

5.3 关于负权边和复杂度陷阱

再强调一次，Dijkstra不能处理负权边。如果你的图里有负权，哪怕只有一条，结果都可能错。判断方法很简单：跑之前扫一遍所有边，有负的就换算法。别心存侥幸觉得"就一条负边应该没事"，贪心的正确性证明依赖非负性，一条负边就能让整个推理失效。

另一个陷阱是稠密图用堆优化反而更慢。当E接近V²时，堆优化的O((V+E)logV)里ElogV这一项会很大，而朴素版的O(V²)此时可能更快。所以选版本要看图的稠密程度，不是堆优化就一定好。

注意：如果只需要求起点到某一个终点的最短路径，可以在堆优化版里加一句——当弹出的节点就是终点时直接break。因为Dijkstra是按距离递增顺序确定节点的，第一个弹出的终点就是最短的，后面不用再算。这个小优化在单终点场景下能省不少时间。

5.4 实测性能对比

我在一台普通笔记本上跑了一组对比测试，节点数从100到5000，边数约为节点数的5倍（稀疏图），结果如下：

可以看到，小规模时两者差不多，甚至朴素版因为常数小还略快；但规模一上来，堆优化的优势就非常明显了。这也印证了前面的选型建议：小图随便写，大图必须堆优化。

6. 从能跑到好用：几个实战经验

代码跑通只是第一步，真正在项目里用起来，还有几个细节值得注意。第一是输入数据的规模评估，拿到问题先估算V和E的量级，再决定用哪个版本，别盲目上堆优化增加代码复杂度。第二是距离数组的类型，如果边权可能很大，累加后超过int范围，要把dist和边权都换成long long，INF也要相应调整成0x3f3f3f3f3f3f3f3f。第三是多组测试数据的初始化，如果程序要处理多组输入，每次都要把head数组重置为-1、edgeCnt归零，否则上一组的数据会污染下一组，这个bug在多测场景下特别常见。

我个人在实际写这类算法时的体会是，先把朴素版写对，再用它去验证堆优化版，是最省时间的调试策略。具体做法是随机生成一批小图，两个版本各跑一遍，对比所有dist值是否完全一致。只要有一个不一致，就说明堆优化版有bug。这个方法帮我抓到过好几次惰性删除判断写反的问题，比盯着代码看高效多了。

最后分享一个小技巧：调试Dijkstra时，把每一轮选出的节点和更新后的dist数组打印出来，和手工推演的结果对照。图小的时候（比如5到8个节点），手工算一遍并不费劲，但能让你对算法的执行流程建立非常直观的感觉。这种感觉一旦建立，以后写任何最短路径相关的变体都会顺手很多。