企业官网建设流程全解析

简介：围绕图结构中的单源点最短路径问题，这份C语言实现资料面向数据结构课程设计、算法入门与GIS/GPS路径规划场景的学习者，重点演示图的创建、存储以及Dijkstra算法求解既定起点到其余顶点的最短路径。压缩包共2个文件，包含1份doc文档与1份cpp源码，整体约139KB，文档可用于梳理算法思路与课程设计说明，源码则便于对照结构体、指针和图存储的实现细节。已有11696人学习下载，说明其在同类课程设计资料中具有一定参考度。读者可从中获得可运行的Dijkstra算法C语言程序框架、图结构定义与单源最短路径计算流程，并参考文档理解算法步骤、变量组织与调试要点；对交通旅游、城市规划、电网架设等路径选择问题，也能借助该实现建立从模型到代码的对应关系，适合作为实验报告撰写和算法复现的参考资料。

1. Dijkstra 的贪心底气：为什么"已经确定的最短距离"可以不再改

最短路径的 Dijkstra 算法最反直觉的地方在于：一个节点出队之后，dist 值就被视为最终答案、再也不用修改，可它给出的偏偏是全局最优解。很多人在写 C 语言实现时，把visited[u] = 1当成可有可无的标记顺手删掉，结果在某些图上跑出的距离比正确答案还大；问题不在代码写错了，而在这个标记背后有一条从未写进教科书的隐含假设：所有边权非负。搞懂这条假设如何支撑整个贪心流程，你写的 Dijkstra 才不是一个靠背下来的模板，而是一个你知道什么时候能信、什么时候必然出错的工具。下面从松弛的数学含义一路拆到手写二叉堆，把这条推理链补完整。

2. 不变量与松弛：dist 数组为什么能一遍收敛

2.1 松弛的本质：dist 存的是上界，不是答案

初学时常有的一种误解，是把dist[v]当成"已经算出来的答案"。它真实的含义要朴素得多：当前已知的、从源点到 v 的某条具体路径的长度。初始化时除源点外全是无穷大，等价于说"我还没找到任何一条能到达它的路径"。

于是dist[v] = min(dist[v], dist[u] + w(u,v))这一行代码，本质上就是把"经过 u 再走一条边"这条新路径和旧路径比一比，取短的那个。这叫松弛（relaxation），名字来自运筹学里的对偶理论，换成大白话说就是"把绷得太松的上界往下勒一勒"。

这个视角能推出两条很关键的性质。

第一条，dist 单调不增。每次松弛要么不变，要么严格变小，绝不会变大。这意味着算法不会来回震荡，收敛是必然的。

第二条，dist 永远是真实最短距离的上界。因为每一个被写进 dist 的值，都对应着一条真实存在的、从源点走过来的路径，而真实最短距离是所有路径里最短的那条，所以dist[v] >= δ(s,v)恒成立（δ 表示真实最短距离）。

有了这两条，正确性问题的提法就变了：不需要证明"算法能找到最短路径"，只需要证明"当算法说某个 dist 是最终答案时，这个上界恰好被压到了真实值"。整个 Dijkstra 的证明工作，其实全部集中在这一点上。

三种距离标签状态对照如下，写代码调试时非常有用：

如果调试时看到某个已确定节点的 dist 后来还想被改小，那一定是别的地方出了问题：要么代码漏了visited判断，要么图里有负权边。

2.2 贪心选择为什么合法：最近未确定点的终局性

现在来啃最关键的一块：凭什么说"未确定点里 dist 最小的那个，它的 dist 就是最终答案"？

用反证法。设当前所有未确定节点中 dist 最小的是 u，假设dist[u] > δ(s,u)，即它不是真正的最短距离。那么真实最短路径存在，且这条路径上必有节点尚未确定（源点已确定，终点 u 未确定，路径连续，所以中间必然有一个从"已确定"跨到"未确定"的边界点）。

设 y 是这条真实最短路径上第一个未确定的节点，x 是 y 在路径上的前驱。因为 y 是第一个未确定的，所以 x 已经确定，dist[x] = δ(s,x)（这是对已确定节点的归纳假设），并且 x 的所有出边在它出队时都被松弛过，因此：

dist[y] <= dist[x] + w(x,y) = δ(s,x) + w(x,y) = δ(s,y)

而 y 在 s 到 u 的最短路径上，所以δ(s,y) <= δ(s,u) < dist[u]。串起来就是dist[y] < dist[u]，这意味着存在一个未确定节点的 dist 比 u 还小，和"u 是未确定点里最小的"直接矛盾。

证明到这里还没结束，得回头看最后一步用了什么：δ(s,y) <= δ(s,u)。这个不等式成立的前提是最短路径上"越往后的节点距离不会变小"，也就是路径长度单调不减。边权非负正好保证这一点。一旦某条边是负的，从 y 走到 u 可能反而让总长度变短，δ(s,y) <= δ(s,u)就翻过来了，整条反证链当场断裂。

这就是 Dijkstra 不能处理负权边的根本原因。它属于结构性的缺陷，并非实现细节上的疏漏。也正因为如此，visited标记可以当成"不可撤销"的变量：一旦置 1，就代表上界已经被夹死，再也不会被松弛改动了。调试时如果看到已确定节点的 dist 发生变化，那基本可以断定负权边混进来了，或者代码里visited的判断位置写错了。

2.3 三张表在 C 里的分工与落地

理论讲完，看代码。下面这版基于邻接矩阵，选点用线性扫描，是理解算法骨架最直接的写法，也最容易在调试器里单步观察：

#include <stdio.h> #define INF 0x3f3f3f3f /* 约 1.06e9，两个相加仍不溢出 int */ #define MAXV 1005 int graph[MAXV][MAXV]; /* 邻接矩阵，无边填 INF */ int dist[MAXV]; /* 当前已知最短路长度上界 */ int visited[MAXV]; /* 1 表示已确定，不可撤销 */ int prev[MAXV]; /* 前驱，用于还原路径 */ void dijkstra(int n, int src) { for (int i = 0; i < n; i++) { dist[i] = INF; visited[i] = 0; prev[i] = -1; } dist[src] = 0; for (int round = 0; round < n; round++) { /* 第一步：选 —— 在未确定点里挑 dist 最小的 */ int u = -1, best = INF; for (int i = 0; i < n; i++) { if (!visited[i] && dist[i] < best) { best = dist[i]; u = i; } } if (u == -1) break; /* 剩下的点全不可达，提前收工 */ /* 第二步：定 —— 此刻 dist[u] 就是终局答案 */ visited[u] = 1; /* 第三步：松 —— 用 u 的每条出边去收紧邻居的上界 */ for (int v = 0; v < n; v++) { if (graph[u][v] == INF || visited[v]) continue; int nd = dist[u] + graph[u][v]; if (nd < dist[v]) { /* 三角不等式被打破才更新 */ dist[v] = nd; prev[v] = u; /* 顺手记账，供路径还原 */ } } } }

三层循环对应算法三个动作，参数含义逐个说清。

round控制最多跑 n 轮，每轮确定一个点，正常情况正好 n 轮跑完，u == -1是给不连通图准备的提前出口。

best和u承担"选最小"的职责，这里是 O(V) 的线性扫描，所以整体复杂度是O(V² + E)；稠密图上 E 接近 V²，这个复杂度反而是最优的一档，后面第 4 章会展开。

第三步的内层循环遍历所有 v 而不是只遍历邻居，是邻接矩阵的固有代价。visited[v]的跳过判断不是优化，是必需项：已确定节点的 dist 已经不可能再被改小，去比较它只是白费力气，更危险的是万一因为浮点误差或溢出真的改动了，会把不变量破坏掉。

prev这张表看起来可有可无，但只要需要输出路径而不只是距离，它就是必需品。还原时从终点一路v = prev[v]倒着走回源点，再反转即可。忘记初始化prev是新手最常见的崩溃来源之一：不初始化时prev里是栈垃圾值，倒推时直接越界。

邻接矩阵版本跑通之后，距离和路径都能拿到。但它有两个硬伤：空间 O(V²) 在 V 上万时直接爆内存，选点 O(V) 在稀疏图上浪费严重。这两个问题分别对应后面两章的存储结构选型和优先队列改造。

3. 存储结构：邻接矩阵、邻接表与数组池，C 里怎么选不翻车

3.1 邻接矩阵：确定性与缓存友好的代价

邻接矩阵唯一的优势是"查边 O(1)"，但这个优势在 Dijkstra 里几乎用不上：算法从来不做"u 和 v 之间有没有边"的点查询，它做的是"把 u 的所有出边过一遍"。用矩阵等于把一次邻居遍历变成了一次全表扫描。

空间账必须先算清。一个 int 占 4 字节，graph[10000][10000]就是 4 × 10⁸ 字节，接近 400MB，在嵌入式或小内存机器上直接分配失败。graph[1000][1000]是 4MB，勉强能接受；graph[500][500]是 1MB，很安全。所以矩阵版的适用范围大致是 V ≤ 2000 且图偏稠密。

不过矩阵也有它不该被低估的地方：内存连续、无指针跳转、缓存命中率高。在 V 只有几百、边却接近完全图的场景里，矩阵版的实测速度常常反超"理论更优"的邻接表加堆版本，因为后者的 log 因子和指针追逐开销在小规模下是纯粹的负担。这是典型的理论复杂度好看、实测翻车的场合，值不值得优化要根据实际数据量判断。

还有两个实现细节容易出错。无向图必须双向填：graph[u][v] = graph[v][u] = w，只填一边跑出来的结果会把一半的边当成不存在。重边（同一对点之间多条边）在矩阵里天然只保留最后一次写入的那条，如果最后写入的不是最小的那条，答案就会偏大；正确做法是写入时取 min，即if (w < graph[u][v]) graph[u][v] = w;。

3.2 邻接表：指针链表与数组池的取舍

邻接表的思路是每个点挂一条出边链表，空间降到 O(V + E)。C 里有两种写法，差别很大。

第一种是教科书式的指针链表，每个边节点malloc一次：

typedef struct EdgeNode { int to, w; struct EdgeNode *next; } EdgeNode; EdgeNode *head[MAXV]; /* 每个点一条链表 */

写法直观，但有两个隐患。一是 E 条边就要malloc一次，十万条边就是十万次系统调用，建图时间可能比算法本身还长；二是节点分散在堆的各处，遍历时缓存极不友好，实测常常比矩阵版还慢。

第二种是竞赛和嵌入式里更常见的"链式前向星"：所有边预先分配在一个连续数组里，用next下标串成链表。本质还是邻接表，但内存一次性拿完、访问局部性好：

#define MAXE 200005 typedef struct { int to, w, next; /* next 是下一条边的数组下标，-1 表示链表结束 */ } Edge; Edge edges[MAXE]; int head[MAXV]; int ecnt = 0; void init_graph(int n) { for (int i = 0; i < n; i++) head[i] = -1; ecnt = 0; } /* 无向图调用两次：add_edge(u,v,w); add_edge(v,u,w); */ void add_edge(int u, int v, int w) { edges[ecnt].to = v; edges[ecnt].w = w; edges[ecnt].next = head[u]; /* 头插法，新边指向旧的链表头 */ head[u] = ecnt++; }

遍历方式是从head[u]出发顺着next走，直到 -1。头插法的副作用是邻居顺序和输入顺序相反，一般无所谓，但如果算法依赖遍历顺序（比如要求相同距离时按编号小的优先），就得改成尾插或者建完再反转。

参数上要盯紧两处。MAXE的估算：无向图的实际边数是输入边数的两倍，写MAXE = 2 * M才够，少写一半就是数组越界的经典翻车现场，而且这种越界往往不立刻崩，而是把相邻的全局变量写坏，症状五花八门，是排查成本最高的一类 bug。ecnt必须在每组数据前重置为 0，多组测试数据不清零，第二组会接在第一组后面继续追加。

3.3 CSR 与稠密稀疏的分界线

如果图是静态的、建好之后只读不写，还有一种更极致的布局叫 CSR（压缩稀疏行）：把所有边的终点按源点分组排成一个连续数组，再用一个offset数组记录每个点的边从哪开始到哪结束。

offset: [0, 2, 5, 6, ...] 点 i 的边在 to[] 中的区间是 [offset[i], offset[i+1]) to: [1, 3, 0, 2, 4, 1, ...] weight: [7, 2, 7, 9, 1, 2, ...]

三个数组全是连续的，没有任何指针，遍历时的访存模式是教科书级的顺序访问。代价是建图要两遍：第一遍统计每个点的出度得到 offset，第二遍填内容；图一旦建好就不能再动态加边。大规模静态图上的最短路，这个布局通常比链式前向星再快一截。

选型的经验分界线大致是这样：V 在几百量级、图接近完全图，用邻接矩阵；V 上千、边数远小于 V²，用链式前向星或 CSR。判断标准不是"哪个更高级"，而是先把 V 和 E 的数量级估出来，再算内存，最后才谈速度。跳过内存估算直接上矩阵，是很多人第一次在真实数据上跑 Dijkstra 时遇到的最主要问题。

4. 优先队列：从 O(V²) 线性扫描到 O(E log V) 二叉堆

4.1 线性扫描版：短、稳、稠密图上并不慢

第 2 章那版代码的内层"选最小"是 O(V)，套在外层 n 轮里就是 O(V²)。这个复杂度听着吓人，但要分场景看：稠密图 E ≈ V²，此时邻接矩阵的松弛部分本来就要 O(V²)，堆优化顶多把选点那部分从 V² 降到 V log V，总复杂度从 V² 变成 V² 量级没本质区别，反而多付了堆的常数开销。

所以线性扫描版在三种情况下仍然是正确选择：V 小于一两千、图稠密、以及代码需要极致简单可靠（比如跑在资源受限的单片机上，连堆的数组都不想额外分配）。它的另一个好处是没有堆这个中间层，出问题时能直接在调试器里看着dist数组一步步变化，排查难度低得多。

真正的性能分水岭出现在稀疏图上。E ≈ 5V 的时候，V² 里的绝大部分工作都浪费在"一遍遍扫描那些根本不可达或者早已确定的点"上，堆优化能把这块砍掉。

4.2 二叉堆加惰性删除：为什么 C 里很少做 decrease-key

堆优化的核心改动只有一处：把"线性扫描找最小"换成"从堆里弹最小"。但这里有个绕不开的问题：松弛成功之后，dist[v]变小了，堆里那个旧记录怎么办？

教科书给的标准答案是 decrease-key：在堆里找到 v 对应的位置，把值改小，然后向上调整。这要求堆里存的是节点编号，并且额外维护一个pos[v]记录每个节点在堆数组中的下标，每次交换元素都要同步更新两边的 pos。多写五六十行，而且每行都可能写错。

工程上更常见的做法是惰性删除：不管旧的，直接 push 一个新的(新距离, v)进堆。堆里因此可能出现同一个 v 的多条记录，弹出时检查一下if (d > dist[v]) continue;，过期记录直接丢弃。

代价是堆的最大尺寸从 V 涨到 E（每次成功松弛入堆一次，成功松弛总次数不超过 E），空间多花一点；收益是代码量减半，且没有 pos 数组这个容易出错的状态。这笔交易在绝大多数场景下划算，所以下面的实现就用惰性删除。

typedef struct { int d, v; } Item; /* d = 距离, v = 节点编号 */ #define MAXHEAP (MAXE * 2) Item heap[MAXHEAP]; int hsize = 0; static void swap_item(int i, int j) { Item t = heap[i]; heap[i] = heap[j]; heap[j] = t; } /* 入堆：放末尾，然后一路上浮到合适位置 */ static void heap_push(int d, int v) { int i = ++hsize; /* 1-indexed，0 号位不用 */ heap[i].d = d; heap[i].v = v; while (i > 1 && heap[i].d < heap[i >> 1].d) { swap_item(i, i >> 1); i >>= 1; } } /* 出堆：取根，把末尾元素搬到根上，然后一路下沉 */ static Item heap_pop(void) { Item top = heap[1]; heap[1] = heap[hsize--]; int i = 1; while (1) { int l = i << 1, r = l | 1, s = i; if (l <= hsize && heap[l].d < heap[s].d) s = l; if (r <= hsize && heap[r].d < heap[s].d) s = r; if (s == i) break; /* 已经比两个孩子都小，停 */ swap_item(i, s); i = s; } return top; }

堆用 1-indexed 数组实现，父节点是i >> 1，左右孩子是i << 1和(i << 1) | 1，这套下标关系是二叉堆最省事的表示法，比 0-indexed 少一层加减。

heap_push的上浮循环条件是"比父亲小就换"，注意必须是严格小于，用<=在大量等距离节点时会造成不必要的交换，虽然不影响正确性但白费时间。

heap_pop的下沉循环里s记录三者中最小的下标，每轮选出最小的孩子和当前节点比较。这里有个容易写错的地方：heap[1] = heap[hsize--]在hsize为 1 时会把根自己赋给自己然后hsize变 0，循环因为l > hsize直接退出，逻辑仍然正确，不需要特判。

MAXHEAP取2 * MAXE是保险值，理论上堆内元素不超过 E 加初始的 1 个，多留一倍防止估算失误导致越界。

主循环改成这样：

void dijkstra_heap(int n, int src) { for (int i = 0; i < n; i++) { dist[i] = INF; prev[i] = -1; visited[i] = 0; } dist[src] = 0; hsize = 0; heap_push(0, src); while (hsize > 0) { Item cur = heap_pop(); int u = cur.v, d = cur.d; if (d > dist[u]) continue; /* 过期记录，丢掉 */ if (visited[u]) continue; /* 已确定，跳过 */ visited[u] = 1; for (int e = head[u]; e != -1; e = edges[e].next) { int v = edges[e].to, w = edges[e].w; if (visited[v]) continue; if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; prev[v] = u; heap_push(dist[v], v); /* 旧的不管，直接压新的 */ } } } }

if (d > dist[u]) continue;是惰性删除的判定核心，d是这条记录入堆时的快照，dist[u]是当前最新值，快照比最新值大就说明它是过期货。少了这一行，一个节点会被当成多个不同节点反复展开，visited判断能兜住一部分，但dist[u]可能已经被后来的更大值覆盖过，结果就错了。

if (visited[u]) continue;在惰性删除下也不能省：一个节点可能先以较大距离入堆、后以较小距离入堆，小的先弹出并置 visited，大的那条稍后弹出时必须跳过。

复杂度上，每条边最多触发一次入堆，堆操作 O(log E)，总时间是 O((V + E) log V)，空间 O(V + E)。对稀疏图这是压倒性优势。

4.3 索引堆与 decrease-key：什么时候值得多写那六十行

惰性删除唯一的代价是堆可能膨胀到 E 条记录。在 E 上百万、内存吃紧的场合，这个开销就不可忽略了。此时索引堆才有意义：堆里只存 V 个节点，pos[v]记录 v 在堆数组中的位置，松弛成功时执行 decrease-key，直接原地把 d 改小然后上浮，同时沿途更新受影响节点的 pos。

索引堆的复杂度是 O((V + E) log V) 但常数更小、内存固定 V。写它的门槛在于 pos 的维护必须和每次 swap 严格同步，漏一处就会导致 decrease-key 找错位置，症状是"偶尔结果偏大"，随机性极强，非常难调。

我的判断标准很朴素：E 在十万以内，惰性删除够用，别折腾索引堆；E 到百万级且内存敏感，再考虑上索引堆，并且必须写对拍脚本验证。为了省几十 MB 内存引入一个难调的组件，在大多数项目里不是划算的交易。至于斐波那契堆那种 O(E + V log V) 的理论最优解，实际常数极大、实现复杂度极高，工程里几乎见不到，了解即可。

5. 避坑与排查：负权、溢出和那些半夜才发现的边界

5.1 数值坑：INF 相加如何把正确答案变成负数

现象：某些不可达节点的 dist 输出是负数或者一个很小的正数；或者整张图的答案都比预期小。

原因：INF定义成INT_MAX（2147483647），松弛时算出dist[u] + w，当dist[u]是 INF 时直接整数溢出，变成负数，这个负数比任何真实距离都小，于是被当成一个"更短的路径"写进 dist 并继续传播。C 语言的有符号整数溢出是未定义行为，实际表现依编译器而定，但"变成负数"是最常见的一种。这种 bug 在只有连通图的测试数据上完全看不出来，一上真实数据就大面积出错。

解决：用0x3f3f3f3f（约 1.06×10⁹）作为 INF。它的妙处是两个这样的数相加约 2.12×10⁹，仍在 int 范围内不溢出，同时它足够大，超过绝大多数题目的合法路径长度。如果边权可能达到 10⁹ 量级，就改用long long并把 INF 设成0x3f3f3f3f3f3f3f3f。另外在松弛前加一道if (dist[u] == INF) continue;是廉价的双保险，代价可以忽略。

5.2 图结构坑：负权、重边与无向图的单向填充

现象一：结果比正确答案大，且在某些特定图上错得离谱。原因：图里有负权边，但用了 Dijkstra。第 2 章的反证链在负权下断裂，已确定节点的距离可能被后来的路径改小，而visited标记阻止了这次更新。解决方案：先扫一遍所有边检查符号，有负权就换 Bellman-Ford 或 Johnson，别试图给 Dijkstra 打补丁，那不是一个能修的问题。如果只是"边权可以为 0"，那没问题，非负包含 0。

现象二：无向图跑出来的距离普遍偏大，某些点干脆不可达。原因：建图时只加了u→v，漏了v→u。解决方案：封装add_edge时区分有向无向，无向图在函数内部连加两次，别指望调用方记得。这个错犯一次记一辈子，属于血泪经验级别。

现象三：同一对点有多条边时，答案偏大。原因：邻接表保留了所有重边本来是没问题的（松弛会自动选最短的那条），但如果为了省事在加边时做了"已存在就跳过"的判断，反而把更短的那条挡掉了。解决方案：邻接表允许重边，什么都不用做；邻接矩阵则必须在写入时取 min。

5.3 状态坑：visited 的时机与路径还原的断链

现象一：把visited[u] = 1写在弹出循环的开头之外、或者写在松弛之后，结果出现节点被重复展开甚至死循环。原因：visited的语义是"这个点的距离已经终局"，它必须在出堆确认后、松弛之前立刻置位，晚一步就可能被同轮的其他更新干扰。解决方案：固定成"弹出 → 判过期 → 判 visited → 置 visited → 松弛"这个顺序，不要为了所谓优化调整。

现象二：距离全对，但打印出来的路径是乱码或者走到一半断掉。原因：prev数组没初始化，不可达节点的 prev 是随机值，倒推时越界；或者只在部分分支里更新了 prev，导致链路不完整。解决方案：所有节点的 prev 初始化为 -1，倒推循环写成while (v != -1 && v != src)，并且对dist[终点] == INF的情况提前返回，不要进入还原逻辑。

现象三：同一份代码在本地跑对，换台机器结果就变。原因：全局数组没清零、ecnt或hsize没重置，多组数据之间状态污染。解决方案：把所有全局状态的重置集中到一个init()函数里，主函数每组数据开头调一次。变量散落在各处各自清零，迟早会漏。

6. 设计取舍：直接用 Dijkstra 之前该问的几个问题

把算法拆到这个程度，会发现 Dijkstra 的价值边界比想象中窄也比想象中宽。窄在它只解决"单源、非负权、静态图"这一种问题；宽在它是大量更复杂算法的内核，A* 是它加了个启发式优先级，双向搜索是它从两端同时跑，分层图最短路是它跑在拆点后的图上。

所以在动手实现之前，有几个判断值得先做。

只求单源单目标时，出堆时发现u == target就可以直接 return，不必把整张图跑完。这个早停在实际场景里能省掉大半工作量，尤其是在社交网络、路网这类目标往往离源点不远的图上。唯一的注意点是路径还原必须用已确定的 prev 链，不能拿半成品 dist 去推。

有可用的启发式估计时，A* 比 Dijkstra 快一个数量级，但前提是启发函数可采纳（不高估真实距离），否则最优性就没了。路网上的直线距离、网格图上的曼哈顿距离都是标准选择；如果没有靠谱的启发式，硬凑一个反而会让结果错得莫名其妙。

存在负权但无负环时，Bellman-Ford 是正解，复杂度 O(VE)；有负环且需要检测时也只能靠它。全源最短路在 V 不大（几百以内）时 Floyd 的三重循环反而最简单可靠，代码十行，没有堆、没有邻接表、没有内存管理。

真正大规模的路网查询，工业界的做法是在预处理阶段做层次化收缩或者打标签，把查询压到微秒级。这类方案的核心思想仍然是"用空间换查询时间"，而 Dijkstra 在里面扮演的是预处理阶段反复调用的基础子程序。

我自己的习惯是：任何一次要实现最短路之前，先把节点数、边数、是否有负权、是否需要路径、是否需要多次查询这五个问题写下来，答案会直接把选型定死，剩下的只是照第 2 到第 4 章的模板填。有一次图省事把MAXE按输入边数写死，忘了无向图要乘二，跑小数据全对，上真实数据时直接数组越界，写坏了相邻的全局变量，排查了整整一个下午才发现是那行宏定义。从那以后我每次建图前都强制走一遍这五个问题的清单，尤其是内存估算和边数上限，再简单的图也不跳过。希望这些内容能帮你少走点弯路。

本文还有配套的精品资源，点击获取