图算法进阶：最短路径、最小生成树、最大流等

教程导读：图算法进阶学什么

一句话定位：本文集系统讲解图算法进阶的三大支柱——最短路径、最小生成树、最大流，从抽象模型（最优性原理、切割性质、流量守恒）讲到算法实现与工程取舍，覆盖 Dijkstra、Bellman-Ford、SPFA、Floyd-Warshall、Johnson、Prim、Kruskal、Ford-Fulkerson、Edmonds-Karp 等经典算法。

这本文集讲什么

图，是描述"关系"最自然的语言。社交网络里人与人的好友关系、城市里道路的阡陌纵横、芯片上电路的走线、物流网络中仓库与仓库之间的运力——只要问题能抽象成"节点 + 边"，图算法就能派上用场。

基础图论（邻接矩阵、邻接表、DFS、BFS）解决的是"能不能到达"的问题。而进阶图算法回答的是三个更尖锐的问题：

1. 怎么走最划算——最短路径。权重可以是距离、时间、费用，Dijkstra 一族的算法给出单源最优解，Floyd-Warshall 和 Johnson 给出全源最优解。
2. 怎么连最省钱——最小生成树。要在所有节点之间建立连通，又想让总边权最小，Prim 和 Kruskal 从两个方向解决了它。
3. 怎么运得最多——最大流。网络中每条管道有容量上限，源点最多能把多少流量送到汇点，Ford-Fulkerson 一族算法和最大流最小割定理给出了答案。

本文集按"概念筑基"的主线组织：每个专题先把抽象模型讲透（为什么贪心是对的、为什么反向边能"反悔"、为什么最大流等于最小割），再落到算法步骤、复杂度、实现细节和选型建议。类比主要取自交通管网、电网和水利系统——这三类基础设施恰好对应三大问题的物理原型。

全书结构总览

图算法进阶知识地图

各章速览

适合谁读

• 学过基础数据结构，能写 DFS/BFS，想进阶到加权图问题的读者；
• 准备技术面试，需要把最短路径、生成树、最大流讲清楚、写出来的工程师；
• 做物流、网络、推荐等方向，需要把业务问题抽象成图模型的从业者。

前置要求很简单：一门编程语言的基础语法（示例用伪代码与 Python 风格描述）、递归的直觉、以及"复杂度大 O 记号"的粗略概念。不需要图论数学背景，涉及定理证明时我们会用直观论证带过。

怎么读这本文集

如果你是第一次接触加权图，请严格按章节顺序读——第 1 章的表示法与遍历是后面所有算法的骨架，第 2 章的松弛操作贯穿全书。如果你有一定基础，可以直接跳到感兴趣的专题：每一章开头的支柱页都标明了前置知识与章节内部的依赖关系。

💡 一个阅读建议：图算法的代码都不长，但"看起来对"和"真的对"之间隔着一堆边界情况——负权边、重边、自环、不连通。每节末尾的要点回顾里专门列了这些坑，动手复现示例时不妨故意踩一踩。

每节的写法遵循同一个模式：先给直觉（为什么需要这个算法），再讲原理（它为什么是对的），最后落到工程实践（什么时候用它、什么时候别用）。概念优先于代码，取舍优先于结论。

常见疑问解答

学这套教程需要数学功底吗？

不需要超过中学的数学。全书唯一密集使用数学的场合是复杂度记号，而我们只要求你读得懂"平方级比线性级慢"这种量级判断。定理证明一律采用直观论证（交换论证、反证法的生活化版本），跳过它们不影响理解算法本身——但读一遍会让你明白"算法为什么敢这么做"，这份底气在面试和排错时非常值钱。

应该用什么语言跟着练？

示例统一用 Python 风格的伪代码描述，语法门槛极低。你完全可以用自己顺手的语言复现——图算法的核心是数据结构选型与循环不变量，与语言无关。若追求性能，C 加邻接表是最贴近算法竞赛实践的选择；若追求开发速度，Python 的字典套字典足以跑通本书全部示例。

三大问题学完之后能接上什么？

顺着本书的路线图：第 4 章的最大流通向费用流、二分图匹配的深化（如带权匹配）；第 3 章的生成树通向树上的高级技巧（树链剖分、最近公共祖先）；第 2 章的松弛思想通向动态规划与 A 星搜索。图算法还是分布式系统（一致性、Raft 选举）、知识图谱、图神经网络的地基——传统图算法给出"精确解"的骨架，机器学习方法在其上做近似与泛化。

每篇的例图和数据需要自己准备吗？

所有例图都直接画在正文里，节点规模控制在 4 到 9 个，一张纸就能手工复演。强烈建议真的动手推一遍——图算法的"懂了"和"会了"之间隔着整整一轮手算。每节末的要点回顾里埋着常见坑的提示，复现时不妨故意触发一次，观察错误输出的形态，比读十遍正确代码记得牢。

关于本教程

全书遵循几条固定约定：复杂度中点数记为 n 或 V、边数记为 E；"松弛"专指最短路径的距离更新动作，"增广"专指最大流的流量推进动作，两者不做混用；伪代码中的"无穷大"指一个足够大的哨兵值，工程实现里要注意溢出。图表配色保持浅色系，实线表示原网络的边，虚线表示残存网络中的反向边或概念性的辅助结构。

图算法的世界远不止这三大问题，但最短路径、最小生成树和最大流是其中最基础的三块基石——掌握它们，二分图匹配、网络流费用流、图着色等更深的主题就都有了抓手。我们从第 1 章开始。