先说一个现象很多人学图论单源最短路一上来就抱着 priority_queue 堆优化版不放觉得朴素版 Dijkstra 是“老古董”。但如果去刷题你会发现当题目明确给出的是稠密图、点数只有几百甚至几千时朴素版才是又快又不容易写错的那一个。尤其是很多 OJ 题解和 CSP、考研机试题目里朴素版 Dijkstra 出现的频率一点都不低。今天这篇就把朴素版从头到尾拆开讲透包含模板、手算例子、初始化细节、常见坑和配套画图工具学完拿去直接做题没问题。1. 看待朴素版 Dijkstra先搞懂它到底解决什么问题1.1 使用场景单源正权最短路Dijkstra 算法解决的核心问题只有一个给定一张带权图指定一个起点 s求 s 到其他所有点的最短路径长度。注意这个词“单源”意思是只从一个源点出发如果题目要求多源就得考虑 Floyd 或者多次跑 Dijkstra 了。它对边权有一个严格前提所有边的权值必须是非负的。这一点再怎么强调都不为过因为算法能成立的根基就是“当前已确定最短路的点以后不可能再被其他点更新得更短”。一旦出现负权边这个根基就会失效。朴素版适合什么样的图呢核心判断标准是稠密图。所谓稠密就是边数 m 接近 n²这时候用邻接矩阵存图最自然算法复杂度 O(n²)和边数无关。反过来如果图很稀疏比如 m 只有几千、n 有十万那是堆优化 Dijkstra 的天下。不同算法适用不同场景不存在谁完全替代谁。1.2 为什么每个算法学习者都要认真过一遍朴素版朴素版 Dijkstra 是理解“贪心 松弛”思想的绝佳载体。把它的执行过程吃透后面再看堆优化版、Prim 算法、甚至动态规划里的很多状态转移都会觉得特别顺畅。做算法题有个规律基础版本不是用来“被淘汰”的而是用来“打底”的。你在 OJ 上搜朴素 Dijkstra 模板题会发现很多题目的 n 范围都在 500 左右比如经典的 HDU 2544 最短路、CSP 历年某些图论小题它们完全能用 n² 写法。写堆优化版当然也能过但调试复杂度反而高还要维护 pair 排序注意比较器细节。朴素版思路直接代码量小考场上一紧张反而更不容易写错。还有一个容易被忽略的点朴素版 Dijkstra 用邻接矩阵时重边的处理方式特别“憨厚”。每次读入 a b c直接w[a][b] min(w[a][b], c)就完了不会像邻接表那样需要处理链式结构。这道 day63 题点名“朴素版”基本就是冲着邻接矩阵去的。2. 核心设计与执行流程两句话就能说清但细节决定成败2.1 用到的数据结构写朴素版需要准备三样东西变量作用类型建议dist[i]起点 s 到点 i 的当前最短距离int或long long视边权范围决定vis[i]点 i 是否已经被确定为“最短路不再变”的点bool数组w[u][v]邻接矩阵存 u 到 v 的边权int初始化为无穷大这里的“无穷大”在 C 里是个经典讲究。我用的是memset(w, 0x3f, sizeof(w))这样每个 int 会变成 0x3f3f3f3f也就是十进制的 1061109567大约 10 亿。这个数比 int_MAX 小很多所以两个 0x3f3f3f3f 相加不会溢出又能当作“大到不可能作为路径”处理。如果你用0x7fffffff作为无穷大dist[u] w[u][v] 一加就爆 int 变成负数直接让你的最短路变成“负权路”炸得天昏地暗。这一点一定要记牢。2.2 算法执行步骤拆解朴素 Dijkstra 经典到什么程度呢它的主循环只需要三个动作反复做 n 次在“还没确定最短路”的点里找dist最小的那个记为 t。把 t 标记为已确定也就是vis[t] true。拿 t 去“松弛”所有能从 t 出发到达的点 v如果dist[t] w[t][v] dist[v]就更新dist[v]。这里的“松弛”两个字是图论黑话理解成“看看能不能通过 t 让路径更短”就行。好比你去一个地方原来知道走直达高速要 80 分钟后来发现先走 30 分钟到中转站、再换乘 40 分钟总共只要 70 分钟那就更新方案。整个过程总共进行 n 次外层循环因为每轮都会确定一个点n 轮后所有点都已确定。每次选最小点需要扫描 n 个点松弛时也可能扫描 n 个点所以时间复杂度是 O(n²)。2.3 为什么贪心在这里必然正确很多人对“每次找最小的那个点就认为它的最短路定了”这件事总觉得不踏实。这里给一个白话说清楚的说法如果所有边权都是非负的那么一个点的 dist 再往后想变小只能通过“某个当前还没确定、dist 更小的点”转一下。可现在你已经选了所有 dist 比它小的未确定点并且用它们松弛过了说明已经不存在能让它再变短的中间点了。因此此刻它的 dist 就是最终答案。这个论证的“命门”就是边权非负。如果有一条负权边哪怕中间点 dist 很大绕一圈后总距离反而可能变小Dijkstra 直接失效。所以写代码前先看题目的边权范围如果出现负数就得换 SPFA 或 Bellman-Ford。3. 从零到 AC 的模板代码每行都有它的道理3.1 完整可运行的 C 代码这里直接给出一份我平时最常用的朴素版 Dijkstra 模板配合注释食用#include bits/stdc.h using namespace std; const int N 510; const int INF 0x3f3f3f3f; int n, m; int w[N][N]; // 邻接矩阵存权值 int dist[N]; // 起点到各点的最短距离 bool vis[N]; // 是否已经确定最短路 int dijkstra(int s) { memset(dist, 0x3f, sizeof(dist)); dist[s] 0; // 起点距离自己为0 for (int i 0; i n; i) { // 第一步找未确定点中dist最小的点 t int t -1; for (int j 1; j n; j) { if (!vis[j] (t -1 || dist[j] dist[t])) { t j; } } // 如果题目保证可达这里不需要判 t -1 vis[t] true; // 第二步用 t 去松弛所有点 for (int v 1; v n; v) { if (!vis[v] dist[t] w[t][v] dist[v]) { dist[v] dist[t] w[t][v]; } } } if (dist[n] INF) return -1; // 不可达 return dist[n]; } int main() { cin n m; memset(w, 0x3f, sizeof(w)); // 矩阵初始化为无穷大 for (int i 1; i n; i) w[i][i] 0; // 自己到自己是0 while (m--) { int a, b, c; cin a b c; w[a][b] min(w[a][b], c); // 处理重边只保留最短的 // 如果是有向图不用加下面这行无向图需要加 w[b][a] min(w[b][a], c); } cout dijkstra(1) endl; return 0; }注意这份模板的 n 是从 1 开始编号的所以循环范围都是1 j n。如果你习惯从 0 编号记得把数组大小开到 N1 后统一改成 0 到 n-1千万别一个从 1 开始一个从 0 开始。3.2 关于 memset 和 INF 的深度说明上面代码里大量出现memset(w, 0x3f, sizeof(w))初学者经常困惑0x3f 不是只有 8 位吗为什么 memset 一个 int 数组会让整个 int 变成 0x3f3f3f3fmemset是按字节填充的。0x3f 是一个字节的值 0b00111111C 会把 int 的四个字节都填上 0x3f最终结果就是 0x3f3f3f3f。这个值的特征我刚才说了足够大、做加法不溢出、方便 memset 批量初始化。如果你使用const int INF 1e9那初始化只能靠循环 fill麻烦一堆。所以我强烈建议保留这个习惯。代码里还有一处容易被忽略的细节我每次松弛前判断了!vis[v]。实际上这个判断不加也可以因为已经被确定最短路的点 v 若还能被更新说明贪心假设被破坏必然有负权边在当前合法题目下不会发生。但写上它有两个好处一是语义更清楚二是万一输入数据真的出现非法负权能提前防止错误传播。加一个条件不会影响复杂度我建议保留。3.3 复杂度与边界判断题目给什么数据范围才适合朴素版说点实际经验当点数 n ≤ 5000 时O(n²) 大概跑 2500 万次操作C 一秒内可以轻松完成n ≤ 10000 时操作数一亿次理论上勉强能过但要看 OJ 时限是否宽松。因此我的经验判断线是n ≤ 5000放心写朴素版尤其是稠密图5000 n ≤ 10000需要看时限建议优先考虑堆优化版n 10000除非边数同样极小否则朴素版大概率超时。再看边数 m。如果题目没说边数范围只给 n 且 n 小这类题大概率就是要你用邻接矩阵朴素版。另外邻接矩阵空间是 O(n²)二维数组开到 5000×5000 大约是 100MB某些 OJ 内存限制 256MB 是能过的但如果 n 到 10000矩阵需要 400MB直接 MLE。这时候哪怕 n² 时间上勉强可行内存也已经把你卡死了只能切邻接表加堆优化。这些细节准备参加 CSP 或蓝桥杯的同学务必注意。4. 手算一轮全过程5 个点的小图彻底跑明白4.1 问题设定看一个 5 个点、6 条边的无向图暂时不用双向边分开列因为无向图本质就是两条有向边1 - 2权 21 - 3权 52 - 3权 12 - 4权 63 - 4权 24 - 5权 3邻接矩阵初始化后w[1][2] 2, w[1][3] 5, w[2][3] 1依次类推自己到自己是 0其余一对都是 INF。起点设为 1目标求 1 到 5 的最短路。4.2 逐步演算记录初始化dist[1] 0dist[2] INFdist[3] INFdist[4] INFdist[5] INF。vis 全部 false。第 1 轮未确定点中 dist 最小的是点 10所以 t 1。标记 vis[1] true。用 1 松弛能更新 2 为 23 为 5。 这时 dist 数组[0, 2, 5, INF, INF]。第 2 轮未确定点中 dist 最小的是点 22t 2。标记 vis[2] true。用 2 松弛发现 dist[2] w[2][3] 2 1 3 5于是 dist[3] 更新为 3dist[2] w[2][4] 2 6 8dist[4] 从 INF 变为 8。 这时 dist 数组[0, 2, 3, 8, INF]。第 3 轮未确定点中现在最小的是点 33t 3。标记 vis[3] true。用 3 松弛dist[3] w[3][4] 3 2 5 8于是 dist[4] 更新为 5dist[3] w[3][5] 3 INF 还是 INF。 这时 dist 数组[0, 2, 3, 5, INF]。第 4 轮未确定点中最小的是点 45t 4。标记 vis[4] true。用 4 松弛dist[4] w[4][5] 5 3 8dist[5] 从 INF 变成 8。 这时 dist 数组[0, 2, 3, 5, 8]。第 5 轮只剩点 5 未确定t 5标记 vis[5] true没有任何点可松弛循环结束。结论 dist[5] 8对应路径是 1 - 2 - 3 - 4 - 5总长 2 1 2 3 8。看起来很顺但注意第 3 轮有个非常关键的转折如果用贪心最初的第一直觉从 1 出发会先认为 2 的 2 是最近的再往后一看发现从 2 绕到 3 反而比直接从 1 到 3 更短。这个过程就是松弛在起作用。每轮都选当前 dist 最小的点就能保证前面已经确定的点覆盖了“绕路”的情况。4.3 从手算推敲算法的一个易错点如果你自己动笔实现很容易在第 1 轮结束后把点 1 的邻居都“定死”这是错的。vis的真正含义是“这个点的最短路已经被确定了”而不是“这个点被访问过”。第 1 轮后点 2 和点 3 虽然被“更新”了但它们还没有成为本轮最小的 t所以vis[2]、vis[3]都应该是 false。只有真正被选中作为 t 的点才置 true。如果你把 vis 当“访问过”用后面第二轮的更新条件会误判导致路径计算错误。这个区别是新手最常见的问题没有之一。5. 实操中的高频问题与排查技巧5.1 重边不取 min 就 WA邻接矩阵里同一个起点终点可能输入很多次例如“1 2 5”和“1 2 3”同时出现。如果不做w[a][b] min(w[a][b], c)这步最后矩阵里存的可能是权值 5 而不是更短的 3导致答案偏大。如果你用邻接表存图重边的处理逻辑就不同你可能需要遍历整个链来找是否存在相同边或者干脆不加判断直接插入多条边让算法自己选。而邻接矩阵天然能“自动合并重边”这也是它在稠密图场景下一个特别舒服的优势。5.2 点编号从 1 开始还是 0 开始很多学校 OJ 题目描述会说“顶点编号为 1 到 n”但另一些题尤其是 Python 爱好者出的题目喜欢从 0 开始。当你写完模板提交发现全 WA第一反应别急着怀疑算法先去查你的循环有没有从 1 扫到 n但数组却开成 0 到 n-1。这种低级错误非常隐蔽因为小规模测试数据可能碰巧没问题一旦出现和起点连接的第一个点为 0 或者 n就会越界或漏算。我的习惯是读题后立刻在注释里写下// 从 1 开始或// 从 0 开始防止写着写着忘记了。5.3 是否可达的判断如果图不保证连通跑完算法后可能存在某些点根本没被更新dist 仍为 INF。这时不能直接输出 INF 本身而应像模板里那样判断dist[n] INF返回 -1。注意判断对象一定是更新后的 dist 数组而不是初始化的 INF。如果你在循环里没有采用if (t -1) break;之类的提前终止算法会继续跑完 n 轮也没问题反正未到达的点之间也无法互相更新。这里还有个小坑当 n 比较大且图中存在大量不可达点时dist[t] w[t][v]这行代码可能执行很多次 INF INF 的运算。好在 0x3f3f3f3f 0x3f3f3f3f ≈ 2.1e9小于 int 最大值 2.147e9不会溢出成正数或负数所以仍然能保持 INF 状态。如果你用更大的 INF比如1e9INF INF 就是 2e9也还在 int 范围内可以但如果你用 INT_MAXINF INF 会直接溢出成负值就出大事了。这一点在堆优化版里尤其要小心。5.4 常见问题速查表现象可能原因解决方式答案比正确答案大重边没有取 min读入时就w[a][b] min(w[a][b], c)答案比正确答案小或出现负数INF 设置过大导致加法溢出使用 0x3f3f3f3f 或 long long输出总是 0把起点到自己的 dist 初始化为 INFdist[s] 0部分情况死循环找不到未访问点但循环没退出加if (t -1) break;或检查编号范围某些点被认为是不可达有向图按无向图处理少了反向边根据题意判定是否加w[b][a]5.5 一个实用的调试技巧如果想肉眼验证每一步可以在每轮循环结束后打印 dist 数组for (int i 1; i n; i) { printf(dist[%d] %d\n, i, dist[i]); }配合你手算的期望结果逐轮对比能很快定位是“找错点”还是“松弛错”。这个方法虽然土但在调试最短路和最小生成树问题时特别有效。6. 可视化辅助学图论时“图该如何在线绘制”学 prim、Dijkstra 这类算法时只看文字容易绕晕。我写算法题解或者自己理解题目经常需要快速画图这里分享几个我在线画图的处理方式。第一个是 CS Academy 的 Graph Editor地址是 csacademy.com/app/graph_editor。它支持你手动添加点、连线、设权值还能一键生成随机图、切换有向/无向。生成之后对着图跑一遍算法模拟比干想舒服得多。另一个常用工具是 Graphviz基于 dot 语言用文本描述边关系然后自动排版生成图片。比如我要表示上面的例子写这样的 dot 文件digraph G { 1 - 2 [label2]; 1 - 3 [label5]; 2 - 3 [label1]; 2 - 4 [label6]; 3 - 4 [label2]; 4 - 5 [label3]; }在本地装 Graphviz 或者使用在线的 webgraphviz 就能渲染出矢量图。虽然这类工具在实际做题时未必需要但对初学图论、CSP 前突击复习的人来说能把抽象问题具象化降低理解门槛。如果你的目标是刷 OJ 而不是做研究不必花大量时间在这些画图工具上理解算法本身才是关键。7. 朴素版之外从一道题如何延伸出更广的解题能力7.1 与堆优化版的选型对比不要以为“稠密图用朴素版稀疏图用堆优化版”只是一句空话。我用一道题来举例假设有 n 1000 个点m 100000 条边每条边权为正。用朴素版复杂度是 n² 100 万次操作用邻接表加堆优化则需要把每个点的边扫描一遍复杂度接近 m log n ≈ 100000 × 10 100 万次操作两者差不多看谁的常数小。再换一个场景n 20000m 200000稀疏图。朴素版 n² 4 亿次堆优化 m log n ≈ 200000 × 15 300 万次差距巨大。而 n 300m 20000 的稠密图呢朴素版只有 9 万次几乎是瞬时堆优化倒也没有问题但代码复杂度上升、调试成本变高没必要。这就是“按图选算法”的意义。7.2 进阶变化不只求最短距离还要记录路径数量有些题目会让你求从起点到终点的最短路径条数。这时朴素 Dijkstra 的骨架不需要变只需要额外准备一个数组 cnt[i]初始化 cnt[s] 1。在松弛时分类讨论如果通过 t 到达 v 的路径比原来更短则 cnt[v] cnt[t]如果二者相等则 cnt[v] cnt[t]。这里比较容易错的地方是数据量一大路径计数可能爆 int用 long long 或模数存储。这类题目最能检验你对算法每一步真正含义的理解。7.3 扩展朴素原理也藏在其他算法里如果你之后学 Prim 最小生成树会发现它的代码和朴素 Dijkstra 惊人地相似同样是每次找最小 dist然后用它去更新周边点区别只在于 dist 的含义从“到起点的距离”换成“到已选点集的最小边权”。结构化地把握这些共性能让你学新算法时“白捡”一半。8. 开头提到的 day63 训练节奏怎么把今天这题真正吃进脑子像标题这类“day63”图论题目通常处于一份系统的刷题计划中。到这个阶段你已经具备建图、遍历的基本功正是攻克单源最短路的最佳时间点。我给你的训练建议就三步第一天看懂并默写朴素版模板第二天把上面 4.2 的手算例子自己做一遍在纸上画出完整的表观察每轮点如何被选出第三天拿 2-3 道标准题重复提交直到能 10 分钟无 bug 地写出完整代码。别小看“默写”这件事。考场上的时间是稀缺资源如果连朴素模板都要临场逐行思考大概率写不完。把模板练成肌肉记忆后你会有更多精力去分析题目本身——这才是真正拉开差距的地方。