企业官网建设流程全解析

先说一个现象：很多人学图论单源最短路，一上来就抱着 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 用到的数据结构

写朴素版需要准备三样东西：

这里的“无穷大”在 C++ 里是个经典讲究。我用的是memset(w, 0x3f, sizeof(w))，这样每个 int 会变成 0x3f3f3f3f，也就是十进制的 1061109567，大约 10 亿。这个数比 int_MAX 小很多，所以两个 0x3f3f3f3f 相加不会溢出，又能当作“大到不可能作为路径”处理。如果你用0x7fffffff作为无穷大，dist[u] + w[u][v] 一加就爆 int 变成负数，直接让你的最短路变成“负权路”，炸得天昏地暗。这一点一定要记牢。

2.2 算法执行步骤拆解

朴素 Dijkstra 经典到什么程度呢？它的主循环只需要三个动作，反复做 n 次：

1. 在“还没确定最短路”的点里，找dist最小的那个，记为 t。
2. 把 t 标记为已确定，也就是vis[t] = true。
3. 拿 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 编号，记得把数组大小开到 N+1 后统一改成 0 到 n-1，千万别一个从 1 开始一个从 0 开始。

3.2 关于 memset 和 INF 的深度说明

上面代码里大量出现memset(w, 0x3f, sizeof(w))，初学者经常困惑：0x3f 不是只有 8 位吗，为什么 memset 一个 int 数组会让整个 int 变成 0x3f3f3f3f？

memset是按字节填充的。0x3f 是一个字节的值 0b00111111，C++ 会把 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，权 2
• 1 - 3，权 5
• 2 - 3，权 1
• 2 - 4，权 6
• 3 - 4，权 2
• 4 - 5，权 3

邻接矩阵初始化后，w[1][2] = 2, w[1][3] = 5, w[2][3] = 1，依次类推，自己到自己是 0，其余一对都是 INF。起点设为 1，目标求 1 到 5 的最短路。

4.2 逐步演算记录

初始化：dist[1] = 0，dist[2] = INF，dist[3] = INF，dist[4] = INF，dist[5] = INF。vis 全部 false。

第 1 轮：未确定点中 dist 最小的是点 1（0），所以 t = 1。标记 vis[1] = true。用 1 松弛：能更新 2 为 2，3 为 5。 这时 dist 数组：[0, 2, 5, INF, INF]。

第 2 轮：未确定点中 dist 最小的是点 2（2），t = 2。标记 vis[2] = true。用 2 松弛：发现 dist[2] + w[2][3] = 2 + 1 = 3 < 5，于是 dist[3] 更新为 3；dist[2] + w[2][4] = 2 + 6 = 8，dist[4] 从 INF 变为 8。 这时 dist 数组：[0, 2, 3, 8, INF]。

第 3 轮：未确定点中现在最小的是点 3（3），t = 3。标记 vis[3] = true。用 3 松弛：dist[3] + w[3][4] = 3 + 2 = 5 < 8，于是 dist[4] 更新为 5；dist[3] + w[3][5] = 3 + INF 还是 INF。 这时 dist 数组：[0, 2, 3, 5, INF]。

第 4 轮：未确定点中最小的是点 4（5），t = 4。标记 vis[4] = true。用 4 松弛：dist[4] + w[4][5] = 5 + 3 = 8，dist[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，比如1e9，INF + INF 就是 2e9，也还在 int 范围内，可以；但如果你用 INT_MAX，INF + INF 会直接溢出成负值，就出大事了。这一点在堆优化版里尤其要小心。

5.4 常见问题速查表

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" [label=2]; "1" -> "3" [label=5]; "2" -> "3" [label=1]; "2" -> "4" [label=6]; "3" -> "4" [label=2]; "4" -> "5" [label=3]; }

在本地装 Graphviz 或者使用在线的 webgraphviz 就能渲染出矢量图。虽然这类工具在实际做题时未必需要，但对初学图论、CSP 前突击复习的人来说，能把抽象问题具象化，降低理解门槛。如果你的目标是刷 OJ 而不是做研究，不必花大量时间在这些画图工具上，理解算法本身才是关键。

7. 朴素版之外：从一道题如何延伸出更广的解题能力

7.1 与堆优化版的选型对比

不要以为“稠密图用朴素版，稀疏图用堆优化版”只是一句空话。我用一道题来举例：假设有 n = 1000 个点，m = 100000 条边，每条边权为正。用朴素版复杂度是 n² = 100 万次操作，用邻接表加堆优化则需要把每个点的边扫描一遍，复杂度接近 m log n ≈ 100000 × 10 = 100 万次操作，两者差不多，看谁的常数小。

再换一个场景：n = 20000，m = 200000，稀疏图。朴素版 n² = 4 亿次，堆优化 m log n ≈ 200000 × 15 = 300 万次，差距巨大。而 n = 300，m = 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 地写出完整代码。

别小看“默写”这件事。考场上的时间是稀缺资源，如果连朴素模板都要临场逐行思考，大概率写不完。把模板练成肌肉记忆后，你会有更多精力去分析题目本身——这才是真正拉开差距的地方。