企业官网建设流程全解析

1. 项目概述：从“点”到“网”的思维跃迁

搞了这么多年算法，我越来越觉得，图论是程序员思维从“线性”到“网络”的一个关键分水岭。之前我们处理数组、链表、树，结构再复杂，也大多有个清晰的“前驱后继”关系。但图不一样，它描述的是“多对多”的复杂关系网络，社交网络的好友关系、地图导航的路径规划、网络拓扑的数据传输，背后都是图在支撑。而图论算法的核心任务之一，就是解决“最短路径”问题：从A点出发，怎么走才能最快（或成本最低）地到达B点？

这次我们聚焦的“算法基础14”，正是图论最短路径算法的入门精华包，它一口气串联了四个经典算法：Floyed（弗洛伊德）、Dijkstra（迪杰斯特拉）、Bellman-Ford（贝尔曼-福特）和SPFA（Shortest Path Faster Algorithm）。这可不是简单的罗列，而是一条清晰的认知升级路径。Floyed让你理解所有点对之间最短距离的全局计算思想；Dijkstra则是在正权图上寻找单源最短路径的“贪心”典范；当图中存在负权边时，Bellman-Ford以其稳健的松弛操作成为可靠的后盾；而SPFA则是Bellman-Ford的队列优化版本，在多数情况下能跑得更快。掌握这四板斧，你就能应对绝大多数面试和实际开发中遇到的加权图最短路径问题了。无论你是正在备战算法竞赛的学生，还是工作中需要处理网络路由、资源调度、关系推荐的开发者，这套组合拳都值得你投入时间彻底吃透。

2. 核心算法思想与适用场景全解析

在深入代码之前，我们必须先弄清楚每个算法“为什么”存在，以及它们各自的地盘在哪里。盲目套用算法，就像用螺丝刀去敲钉子，事倍功半。

2.1 Floyed算法：全局视野的“多源”最短路径

Floyed算法的核心思想是动态规划，它要解决的是“所有顶点对”之间的最短路径问题。想象一下，你有一张城市交通图，需要快速查出任意两个城市之间的最短驾车距离，Floyed就是干这个的。

它的思路非常巧妙：我们假设顶点编号从1到n。算法维护一个二维数组dist[i][j]，代表从点i到点j的当前已知最短距离。初始时，dist[i][j]就是邻接矩阵中记录的边权（如果i和j直接相连），否则就是无穷大（INF），并且dist[i][i] = 0。

Floyed的三重循环是它的灵魂：

for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (dist[i][k] != INF && dist[k][j] != INF && dist[i][j] > dist[i][k] + dist[k][j]) { dist[i][j] = dist[i][k] + dist[k][j]; } } } }

这个k到底是什么？你可以把它理解为“中转站”。整个算法的过程就是：允许使用前1个顶点作为中转，更新一遍最短距离；再允许使用前2个顶点作为中转，再更新一遍……直到允许使用所有n个顶点作为中转。当k循环完成后，dist[i][j]存储的就是从i到j，允许经过图中任意顶点的最短路径长度。

它的优缺点和适用场景非常明确：

• 优点：思想简单，代码极其简短（就三重循环），能一次性求出所有点对的最短路径。
• 缺点：时间复杂度是O(n³)，空间复杂度O(n²)。这意味着当顶点数n较大时（比如超过500），它的计算成本会变得非常高。
• 适用场景：稠密图（边数接近n²），且顶点规模不大（通常n<200）时，用它非常方便。或者在你确实需要所有点对最短路径结果时。

注意：Floyed算法不能处理带有“负权回路”的图（即边权总和为负的环），因为这样的图中不存在最短路径（可以无限绕环使距离趋于负无穷）。但它可以处理带有负权边但没有负权回路的图。

2.2 Dijkstra算法：正权图的“单源”贪心寻路

如果说Floyed是上帝视角，那Dijkstra就是一位从起点出发的稳健探索者。它解决的是“单源最短路径”问题：从一个固定的源点s出发，到图中所有其他顶点的最短距离。

Dijkstra算法的核心是“贪心”策略。它维护一个集合S，代表已经找到最短路径的顶点。初始时，S中只有源点s。然后，它不断地从尚未确定最短路径的顶点集合中，选择一个距离源点s最近的顶点u，将其加入S，并用u去“松弛”其所有邻居顶点v的距离。

为什么选择“最近”的顶点？这里用到了一个关键性质：在所有边权都为非负数的图中，当前距离源点最近的那个顶点，它的最短路径距离不可能再被其他更远的顶点更新了。这是Dijkstra算法正确性的基石，也决定了它不能处理负权边。

它的经典实现有两种：

1. 邻接矩阵实现：每次找最小距离顶点需要遍历所有顶点，总复杂度O(n²)，适合稠密图。
2. 邻接表 + 优先队列（堆）优化：这是必须掌握的优化版本。我们用一个小根堆（C++中用priority_queue）来维护当前未确定顶点的距离，每次取堆顶（距离最小的顶点）只要O(log n)。总复杂度可以优化到O((n+m) log n)，其中m是边数，适合稀疏图。

适用场景：边权均为非负的图，且你只关心从一个源点到其他所有点的最短路径。这是实际应用中最常见的算法，比如地图导航（距离、时间成本均为正）、网络路由协议（如OSPF）。

2.3 Bellman-Ford算法：负权图的可靠卫士

当图中存在负权边时，Dijkstra的贪心策略就失效了，因为“当前最近”的顶点可能通过一个负权边变得更近。这时就需要Bellman-Ford算法。

它的思想比Dijkstra更“暴力”，也更具普适性：对图中的所有边，进行n-1轮松弛操作。每一轮都尝试用所有边去更新起点到各个顶点的最短距离。为什么是n-1轮？因为在没有负权回路的情况下，最短路径最多包含n-1条边（否则就会重复经过某个顶点，形成环，而正权环不会使路径更短，负权环不允许存在）。

算法结束后，再进行第n轮松弛。如果第n轮还能成功松弛任何一条边，那就说明图中存在负权回路，从源点出发的最短路径无法定义。

它的优缺点：

• 优点：能够处理带有负权边的图，并能检测出负权回路。代码实现简单，不依赖于复杂的数据结构。
• 缺点：时间复杂度高达O(n*m)，在稀疏图上也比堆优化的Dijkstra慢很多。
• 适用场景：图中存在负权边，或者你需要检测负权回路。例如，在某些金融网络、差分约束系统中，边权可能代表增益或损耗，允许为负。

2.4 SPFA算法：Bellman-Ford的队列优化

SPFA (Shortest Path Faster Algorithm) 可以看作是Bellman-Ford的“聪明版”。Bellman-Ford每轮都无差别地松弛所有边，效率低下。SPFA观察到：只有那些在前一轮松弛中距离被更新的顶点，才有可能在这一轮中去更新它的邻居。

因此，SPFA使用一个队列来维护这些“距离被更新过的顶点”。流程如下：

1. 源点入队。
2. 取出队首顶点u，松弛它的所有出边。如果某个邻居v的距离被更新了，并且v不在当前队列中，则将v入队。
3. 重复步骤2，直到队列为空。

这本质上是一个宽度优先搜索（BFS）的思想，但队列中的顶点可能会重复入队。SPFA的平均时间复杂度被认为是O(km)，其中k是一个常数，在随机图上通常很小，因此效率远高于朴素的Bellman-Ford。但在最坏情况下（比如精心构造的网格图），它可能退化到O(nm)，和Bellman-Ford一样。

适用场景：同样是处理带有负权边的图，且图中没有负权回路。在大多数非构造性数据中，SPFA的效率很高，是竞赛和笔试中处理负权图的常用选择。但它不稳定，且无法直接判断负权回路（需要记录每个顶点的入队次数，超过n次则可能存在负环）。

3. 算法核心实现细节与代码剖析

理解了思想，我们来看看如何把它们变成可运行的代码。这里我会给出最经典和实用的实现，并附上关键注释。

3.1 Floyed算法的标准实现与路径记录

Floyed的实现非常固定。我们通常用邻接矩阵存储图，并用一个很大的数（如0x3f3f3f3f）代表无穷大INF。

#include <cstring> using namespace std; const int N = 210; // 根据题目最大顶点数设定 const int INF = 0x3f3f3f3f; int dist[N][N]; int n, m; // n顶点数，m边数 void floyed() { // 初始化 for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (i == j) dist[i][j] = 0; else dist[i][j] = INF; } } // 读入边 for (int i = 0; i < m; i++) { int a, b, w; cin >> a >> b >> w; dist[a][b] = min(dist[a][b], w); // 处理重边，保留最短的 // 如果是无向图，需要加上 dist[b][a] = min(dist[b][a], w); } // 核心三重循环 for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { // 防止溢出，判断中转点是否连通 if (dist[i][k] < INF && dist[k][j] < INF) { dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); } } } } }

如何记录具体路径？Floyed算法也可以记录路径，需要额外一个path[i][j]数组，在更新dist[i][j]时，记录下这次更新是通过哪个中转点k实现的（即path[i][j] = k）。查询i到j的路径时，需要递归地查找path[i][j]，拼接出完整路径。不过由于Floyed本身复杂度高，且路径记录稍显繁琐，在实际需要具体路径的场景下，更常用的还是Dijkstra。

3.2 Dijkstra算法的邻接表+堆优化实现

这是你必须熟练掌握的版本，99%的正权图单源最短路问题都用它。

#include <cstring> #include <iostream> #include <queue> #include <vector> using namespace std; typedef pair<int, int> PII; // first: 距离, second: 顶点编号 const int N = 100010, INF = 0x3f3f3f3f; int n, m; int h[N], e[N], w[N], ne[N], idx; // 邻接表存储图 int dist[N]; bool st[N]; // 标记是否已确定最短距离 void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; } int dijkstra(int start) { memset(dist, 0x3f, sizeof dist); dist[start] = 0; priority_queue<PII, vector<PII>, greater<PII>> heap; // 小根堆 heap.push({0, start}); // 距离放前面，pair默认按first排序 while (heap.size()) { auto t = heap.top(); heap.pop(); int ver = t.second, distance = t.first; // 如果这个点之前已经用更短的距离更新过了，当前这个是冗余的，直接跳过 if (st[ver]) continue; st[ver] = true; // 标记为已确定 // 用当前确定的点ver，去更新它的所有邻居 for (int i = h[ver]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] > distance + w[i]) { dist[j] = distance + w[i]; heap.push({dist[j], j}); // 新的距离入堆 } } } // 如果dist[n]仍然是INF，说明起点无法到达n号点 if (dist[n] == INF) return -1; return dist[n]; } int main() { memset(h, -1, sizeof h); // 邻接表头初始化 cin >> n >> m; while (m--) { int a, b, c; cin >> a >> b >> c; add(a, b, c); // 如果是无向图，需要 add(b, a, c); } cout << dijkstra(1) << endl; // 计算从1号点到n号点的最短距离 return 0; }

几个关键点：

1. 堆中冗余处理：if (st[ver]) continue;这行至关重要。因为一个顶点可能被多次加入堆（每次距离更新都加入），但只有第一次从堆中取出时，它的距离才是最终确定的最短距离。后续再取出的都是历史更大的值，直接跳过。
2. 复杂度：每个顶点最多入队出队一次（被标记st后不再处理），每次出队需要遍历其所有边。总操作次数约为遍历所有边，每次堆操作O(log n)，故为O(m log n)。
3. 无向图：记得添加双向边。

3.3 Bellman-Ford算法的标准实现与负环检测

Bellman-Ford的模板性也很强，通常用结构体数组存储所有边。

#include <cstring> #include <iostream> using namespace std; const int N = 510, M = 10010, INF = 0x3f3f3f3f; struct Edge { int a, b, w; } edges[M]; int n, m, k; // n点，m边，k代表最多经过k条边（有时是问题限制） int dist[N]; int last[N]; // 备份数组，防止“串联更新” int bellman_ford(int start) { memset(dist, 0x3f, sizeof dist); dist[start] = 0; // 进行k次松弛操作（如果求1到n不超过k条边的最短路） // 如果求普通最短路，则进行n-1次 for (int i = 0; i < k; i++) { memcpy(last, dist, sizeof dist); // 备份上一轮结果 for (int j = 0; j < m; j++) { int a = edges[j].a, b = edges[j].b, w = edges[j].w; // 使用上一轮的距离last[a]来更新，避免本轮更新的结果影响同轮其他边 if (last[a] != INF && dist[b] > last[a] + w) { dist[b] = last[a] + w; } } } // 检测负权回路：理论上再进行第n次松弛，如果还能更新，则有负环 // 但通常题目会说明，这里返回结果 if (dist[n] > INF / 2) return -INF; // 因为负权边更新，INF可能会略微减小 return dist[n]; } int main() { cin >> n >> m >> k; for (int i = 0; i < m; i++) { int a, b, w; cin >> a >> b >> w; edges[i] = {a, b, w}; } int res = bellman_ford(1); if (res == -INF) puts("impossible"); else cout << res << endl; return 0; }

关键点解析：

1. 备份数组last：这是Bellman-Ford实现中非常容易出错的地方。在第i轮松弛中，我们必须使用第i-1轮结束后的距离数组来更新本轮。如果直接用dist数组更新，可能会出现“串联更新”，即本轮刚被更新的点，又立即去更新其他点，这相当于在一次迭代中使用了超过一条边，违背了“最多经过i条边”的限制（当k=n-1时求普通最短路影响不大，但为了逻辑清晰和适应限制边数的问题，强烈建议始终使用备份）。
2. 负环检测：上述代码完成了k次松弛。如果要检测从起点出发是否能到达负环，可以在k=n-1次松弛后，再执行一次松弛操作（第n次），如果任何一条边还能被松弛，则说明存在从起点可达的负权回路。
3. INF判断：由于存在负权边，dist可能从INF被更新为一个略小于INF的值（如INF - 5）。所以判断不可达时，常用if (dist[n] > INF / 2)而不是dist[n] == INF。

3.4 SPFA算法的队列优化实现

SPFA的实现和BFS很像，但需要维护距离数组。

#include <cstring> #include <iostream> #include <queue> using namespace std; const int N = 100010, INF = 0x3f3f3f3f; int n, m; int h[N], e[N], w[N], ne[N], idx; int dist[N]; bool st[N]; // 标记顶点是否在队列中，防止重复入队 void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; } int spfa(int start) { memset(dist, 0x3f, sizeof dist); dist[start] = 0; queue<int> q; q.push(start); st[start] = true; // 在队列中 while (q.size()) { int t = q.front(); q.pop(); st[t] = false; // 出队，标记为不在队列中 // 遍历t的所有出边 for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] > dist[t] + w[i]) { dist[j] = dist[t] + w[i]; // 如果j不在队列中，则入队 if (!st[j]) { q.push(j); st[j] = true; } } } } if (dist[n] == INF) return -INF; return dist[n]; } // 判断是否存在负环（从任意点出发可达的负环） bool spfa_negative_cycle() { // 初始化所有点距离为0，并全部入队 // 因为负环可能从任意点出发，所以需要把所有点都作为起点考虑 queue<int> q; for (int i = 1; i <= n; i++) { q.push(i); st[i] = true; } int cnt[N] = {0}; // 记录每个顶点的入队（松弛）次数 while (q.size()) { int t = q.front(); q.pop(); st[t] = false; for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] > dist[t] + w[i]) { dist[j] = dist[t] + w[i]; cnt[j] = cnt[t] + 1; // 更新松弛次数 if (cnt[j] >= n) return true; // 如果松弛次数达到n，说明有负环 if (!st[j]) { q.push(j); st[j] = true; } } } } return false; } int main() { memset(h, -1, sizeof h); cin >> n >> m; while (m--) { int a, b, c; cin >> a >> b >> c; add(a, b, c); } int res = spfa(1); if (res == -INF) puts("impossible"); else cout << res << endl; return 0; }

SPFA的要点：

1. st数组的作用：st在这里标记顶点是否在队列中，而不是像Dijkstra那样标记是否“已确定”。目的是防止同一个顶点在距离被多次更新时，被重复加入队列，造成无效操作。一个顶点出队后，如果后续又被其他点更新了距离，它可以再次入队。
2. 负环检测：通用的SPFA负环检测需要做一些改动。我们需要初始化所有点的距离为0（相当于建立一个“超级源点”连向所有点且边权为0），并全部入队。然后记录每个顶点被松弛的次数cnt。根据Bellman-Ford原理，最短路径最多经过n-1条边，因此一个顶点最多被松弛（入队）n-1次。如果某个顶点的入队次数达到n，则说明存在负环。注意，这里的dist数组初始值不影响负环的判断，因为负环的存在会使距离不断减小。
3. 效率：在随机图上，SPFA通常很快。但在某些特殊构造的图（如网格图、菊花图）上，它可能退化到O(nm)。因此，在正权图问题上，保险起见优先使用Dijkstra。

4. 四大算法对比与选型指南

纸上得来终觉浅，绝知此事要躬行。理解了原理和代码，我们还需要一张清晰的“决策地图”，来指导我们在不同场景下该用哪个算法。

选型决策流程：

1. 第一步：确定问题类型

   • 需要所有点对之间的最短路径？-> 考虑Floyed。但务必先看顶点数n，如果n>500，就要警惕O(n³)的复杂度可能超时。
   • 只需要从一个起点到其他点的最短路径？-> 进入第二步。

2. 第二步：检查边权

   • 图中所有边权都是非负数？-> 毫不犹豫，选择堆优化Dijkstra。这是效率最高、最稳定的方案。
   • 图中存在负权边？-> 进入第三步。

3. 第三步：处理负权边

   • 如果题目明确保证没有负权回路，且你对效率有要求（比如竞赛），可以尝试SPFA。但要知道它有被特殊数据卡的风险。
   • 如果题目需要检测负权回路，或者你追求代码的稳定性和普适性（比如笔试、工程），使用Bellman-Ford。它的O(n*m)复杂度是稳定的上界。
   • 如果问题有**“最多经过k条边”**的限制，必须使用Bellman-Ford，并且配合备份数组last来实现。

一句话口诀：正权单源用Dijkstra，负权检测用Ford，全源小图用Floyed，随机负权试SPFA。

5. 实战中的常见“坑点”与调试技巧

理论很美好，调试很残酷。下面这些是我和很多同行在实战中踩过的坑，希望能帮你省下几个小时甚至几天的调试时间。

5.1 无穷大INF的设定与判断

这是一个初学者极易出错的地方。

• 设定：通常用0x3f3f3f3f。这个数约等于10^9，满足大多数题目对边权范围的要求（一般不超过10^9）。更重要的是，0x3f3f3f3f的每个字节都是0x3f，用memset(dist, 0x3f, sizeof dist)可以快速将整个数组初始化为这个值。而且，两个0x3f3f3f3f相加不会溢出到负数（仍在int范围内）。
• 判断：
  • 在Dijkstra (正权图)中，如果dist[t] == INF，可以认为从起点无法到达t点。
  • 在Bellman-Ford/SPFA (可能有负权)中，由于负权边的存在，INF可能被更新为一个略小于INF的值（例如INF - 5）。此时判断不可达应该用if (dist[t] > INF / 2)。这是一个经验值，因为边权之和通常不会大到使INF减少超过一半。

5.2 重边和自环的处理

图的输入数据往往不是“干净”的。

• 重边：两个顶点之间可能存在多条直接相连的边，且权值不同。对于最短路径问题，我们显然只关心权值最小的那条。
  • 邻接矩阵：在读入边时，使用g[a][b] = min(g[a][b], w)。
  • 邻接表：直接添加多条边即可，算法本身（如Dijkstra）在松弛时会自动选取最小的那条，因为我们会用min操作更新dist。
• 自环：从自己指向自己的边。在正权图中，自环权值为正，不会影响结果（因为dist[i] + w > dist[i]）。在负权图中，负权自环会形成负环，需要算法检测出来。

5.3 无向图与有向图

这是一个概念性错误，但一旦写错，调试起来非常痛苦。

• 无向图意味着边是双向的。在存储时，需要添加两条有向边：add(a, b, w); add(b, a, w);。
• 很多题目描述是“道路”，这通常暗示是无向图。而“单向街道”、“航线”则是有向图。务必仔细审题。

5.4 Dijkstra堆优化中的“冗余点”判断

这是堆优化Dijkstra的灵魂代码，也是我见过最多的错误之一。

auto t = heap.top(); heap.pop(); int ver = t.second, distance = t.first; if (st[ver]) continue; // ！！！就是这行！！！ st[ver] = true; ...

为什么必须有这行？因为一个顶点ver的距离可能被多次更新（每次更新都会将其{new_dist, ver}压入堆中）。但只有第一次从堆中弹出的那个distance才是它最终确定的最短距离。后面再弹出的同顶点ver，其distance必然大于或等于之前确定的值，是“冗余”的。如果不跳过，就会用这个过时的、更大的距离去松弛邻居，虽然不会导致错误结果（因为dist[j] > distance + w条件可能不成立），但会做大量无用功，严重降低效率，甚至可能导致超时。

5.5 Bellman-Ford的“串联更新”问题

在有限制边数（比如最多经过k条边）的最短路问题中，必须使用备份数组last。

memcpy(last, dist, sizeof dist); // 备份上一轮的结果 for (所有边) { // 用last[a]来更新dist[b]，而不是用dist[a]！ if (last[a] != INF && dist[b] > last[a] + w) { dist[b] = last[a] + w; } }

如果不备份，在同一轮循环中，前面边更新的dist[a]可能会被后面的边用到，这就相当于一条路径在本次迭代中使用了超过一条边，违反了“最多经过i条边”的限制。

5.6 调试技巧：打印状态与构造小数据

当你的程序输出错误或者超时时：

1. 打印中间状态：在算法关键步骤后，打印dist数组。对比手动模拟的小样例，看看是从哪一步开始出错的。
2. 构造最小反例：如果提交后WA（Wrong Answer），尝试自己构造一个小的测试用例（n=3, m=4这种），手动计算正确结果，然后看你的程序输出是什么。这是定位逻辑错误最有效的方法。
3. 检查初始化：dist数组、邻接表头h数组是否初始化了？INF设置是否正确？
4. 检查输入：是无向图还是有向图？有没有处理重边？顶点编号是从0开始还是1开始？
5. 复杂度估算：在动手前，先根据题目给的n和m的范围，估算一下你选择的算法是否会超时。比如n=1000，Floyed的O(10^9)运算量基本会超时。

6. 从算法到应用：典型场景延伸思考

掌握了这四种算法，就像拿到了四把不同的钥匙，可以打开许多实际问题的大门。

• Dijkstra的变种：它求的是最短距离，但如果边权代表的是时间、成本、风险概率呢？只要权值非负，且你定义的“最短”满足可加性和非负性（距离+距离还是距离，且不为负），Dijkstra的思想依然适用。例如，在网络延迟、物流成本计算中广泛应用。
• Floyed的额外收获：Floyed算法结束后得到的dist矩阵，不仅是距离，还可以用来解决“传递闭包”问题。如果把边权定义为“是否连通”（连通为1，不连通为INF），那么Floyed算法就可以判断图中任意两点是否连通（dist[i][j] < INF则连通）。这常用于社交网络中的“朋友的朋友”关系推断。
• Bellman-Ford与差分约束：这是Bellman-Ford算法一个非常重要的应用领域。差分约束系统将一系列形如x_i - x_j <= c_k的不等式转化为图论中的边(j -> i, 权值 c_k)。求该系统的一个可行解，等价于在图中添加一个超级源点后，求该点到所有点的最短路径（如果存在负环则无解）。这为许多涉及不等式约束的规划问题提供了高效的图论解法。
• SPFA与网络流：在一些网络流算法（如最小费用最大流）中，需要频繁地在残量网络上寻找最短（最小费用）增广路。由于费用可能为负（回流），Dijkstra无法使用，而SPFA因其在一般图上的高效性，常被用作寻找最短增广路的子过程。

算法的学习从来不是孤立的。把这四个最短路径算法吃透，你不仅解决了“怎么走最短”的问题，更重要的是，你掌握了“贪心”、“动态规划”、“松弛”、“迭代逼近”这些核心的算法设计思想。下次当你遇到一个新的、看似复杂的问题时，不妨想想：这个问题能建模成图吗？顶点和边代表什么？权值是什么？求的是什么？一旦完成了这个建模过程，你的武器库里就已经有现成的工具可以选择了。