网络流理论在理论计算机科学、运筹学和离散数学等学科中均有应用，可用于货物运输建模和计算机视觉图像分割等众多问题。本书主要源于康奈尔大学的网络流算法课程讲义，包含出版年代较早的经典书籍中未能涵盖的新研究成果。本书采用简洁且统一的视点，讨论解决网络流问题的多种组合算法、多项式算法及其分析，涵盖最大流、最小代价流、广义流、多物流和全局最小割集等，还介绍了关于计算电流的新研究成果及其在经典问题上的应用。本书可作为面向研究生的网络流算法教材，也适合该领域的研究人员参考。

基于康奈尔大学相关课程讲义撰写，涵盖该领域新的研究成果

拾人花卉，系之一束；他供鲜花，我献彩带。
——Montaigne

网络流方面的任何新书似乎都应说明其存在的合理性，因为该领域的权威著作早已出版。我所参考的书籍《网络流：理论、算法和应用》(Network Flows: Theory, Algorithms, and Applications) 已于 1993 年出版。该书作者为 Ahuja、Magnanti 和 Orlin[4]，他们是网络流算法领域理论研究和实践应用的先驱。我用该书作者姓名的首字母 AMO 来代表此书。20 世纪 80 年代末至 90 年代初是研究网络流问题的组合算法和多项式算法的黄金时期。AMO 不仅讨论了当时已完成的大部分研究，还给出了网络流领域的广泛综述，其内容贯穿网络流理论研究和实际应用。既然如此，为何还需写此书？我有下面三方面的理由。
第一：关注点问题。我在写另一领域的严谨性书籍 [206] 时意识到，书籍内容很难兼顾“准确严谨” 和 “简洁明了”。AMO 无疑是前者，本书的目标是后者。本书主要关注网络流问题的组合算法、多项式算法及其分析。在康奈尔大学运筹学和信息工程学院任教期间，我教过几次网络流算法方面的研究生课程，本书内容源于对这些课程内容的提炼。该课程主要面向运筹学和计算机科学系的学生，也有电气和土木工程系的部分学生。从教学观点来看，需做点取舍，以保证本书的大部分内容可在一学期内讲完。
此外，由于本书是课堂教学的成果，其涵盖的知识点是一次授课所能讲完的内容。因此，太长或太复杂而无法在一次授课中讲完的知识点，本书都不涵盖。我不太关注网络流理论中的某些领域，比如没有多项式运行时间的网络流应用和算法等。对于本书未涉及的某些网络流理论部分，感兴趣的读者可参阅 AMO。
第二：提供一些 AMO 没有涉及的知识。对最大流问题和最小代价环流问题，虽然本书所提的算法 AMO 也有涉及，但本书给出了一些重要的特殊情形。如前所述，虽然 20 世纪 80 年代末至 90 年代初是研究网络流算法的黄金时代，但该领域在过去 25 年里的研究成果是 AMO 无法涵盖的。
1998 年，Goldberg 和 Rao 所发表的论文 [98] 就是一个著名的研究成果。对最大流问题，他们给出了至今为止在理论上仍被认为最快的算法。1991 年，Wallacher[201] 关于最小代价环流问题的算法是另一个研究成果，该算法具有相当简单的分析。此外，AMO 出版时，针对某些流问题，一些多项式算法正好脱颖而出。显然，AMO 无法涵盖这些算法。
我主要思考的是全局最小割集、广义最大流和多物流等问题的算法。近年来，内点方法在网络流问题的特殊应用中产生了一些快速算法，但这些算法不是组合算法，因此，它们不在本书的选取范围内。本书还包含了一些与电流经典主题相关的成果。
第三：情不自禁。我的主要研究兴趣是组合算法和多项式算法，但在网络流领域，除有一项研究成果外 [173]，几乎一无所获。所以，作为一位公正的旁观者，我可以说，该领域是一个优美且存在一些有用算法思想的领域，这些算法思想以一种令人愉悦的方式相互支持着。
用前面引述的 Montaigne 的话来说，写本书的目的就是做选择和重组，尽我所能地展现一些算法及其分析的美妙之处。希望读者和我一样欣赏这最终呈现的花束。

David P. Williamson
纽约，伊萨卡
2019 年 1 月

计算机\计算理论

自1962年L. R. Ford和D. R. Fulkerson的著作引入网络流理论以来，半个多世纪过去了，这个领域仍然是活跃且有吸引力的。本书基于康奈尔大学的课程材料撰写，对大多数重要的主题进行了简明扼要的描述，包括新的研究进展。本书非常适合用于与算法和优化相关的研究生课程。
—— Toshihide Ibaraki，京都信息大学院大学
这是一本简明易懂的网络流算法书，涵盖经典知识和新的研究成果。对于网络流算法课程，这是一本完美的教材及参考书。它将成为我书架上的常备读物。
—— Kurt Mehlhorn，马克斯·普朗克研究所
本书包括许多带证明的引理和定理，为网络流问题的各类组合算法提供了简洁的描述，并包括许多在其他教科书中找不到的主题。强烈建议学生和研究人员阅读本书。
—— S. V. Nagaraj，SIGACT News
作者简介
大卫·P. 威廉姆森（David P. Williamson）　康奈尔大学信息科学系主任、运筹学和信息工程学院教授，ACM会士，SIAM会士。他在离散优化方面的研究获得了多个奖项，包括2000年由美国数学协会和数学规划协会赞助的Fulkerson奖。他与David B. Shmoys合著的The Design of Approximation Algorithms（Cambridge, 2011）获得了2013年的INFORMS Lanchester奖。他在多个编委会任职，曾任SIAM Journal on Discrete Mathematics的主编。
译者简介
吴向军　博士，中山大学副教授。主要研究方向为人工智能和算法设计等，近年来主要从事智能规划领域的研究和规划系统的设计与开发。

[美]大卫·P. 威廉姆森（David P. Williamson） 著：---作者简介---
大卫·P. 威廉姆森（David P. Williamson） 康奈尔大学运筹学和信息工程学院教授，ACM会士，SIAM会士。他在离散优化方面的研究获得了多个奖项，包括2000年由美国数学协会和数学规划协会赞助的Fulkerson奖。他与David B. Shmoys合著的The Design of Approximation Algorithms（Cambridge, 2011）获得了2013年的INFORMS Lanchester奖。他在多个编委会任职，曾任SIAM Journal on Discrete Mathematics的主编。

---译者简介---
吴向军 博士，中山大学副教授。主要研究方向为人工智能和算法设计等，近年来主要从事智能规划领域的研究和规划系统的设计与开发。

2020，爱你爱你！多么浪漫美好的岁月，任何人都可挥洒自己的想象。在我们准备欢度春节之际，也恰是那看不见的怪兽悄悄偷袭我们之时。在这突如其来的疫情期间，有些想大展宏图的人生戛然而止，有些想展翅翱翔的梦想被禁锢了翅膀。疫情面前，各行各业都在为抗疫做出各自的贡献。有人捐献财物，有人奉献时间，有人不幸付出生命。我能力有限，能做点什么呢？
2020 年年初，有幸承担本书的翻译工作，我想还是在翻译中奉献一点时间和有限的知识吧。
. 奉献时间：读者在阅读时都希望能在较短时间内理解和掌握算法的基本思想，而原书中习惯大段落地叙述某些知识点，这可能与我们的阅读习惯不一致。所以，在不违反原文含义的原则下，我对某些段落进行了整理，用小段落或项目符号的形式呈现原书中的知识点，努力使译文符合我们的阅读习惯。译者多花一点时间来整理，读者就可能少花一点时间来理解。译者希望这是间接向读者奉献时间。
. 奉献知识：本书内容是对网络流算法的描述和证明。在算法描述方面，作者根据上下文省去了一些信息，在译文中则尽量显式地将其表达出来，使算法描述具有一定的独立性。根据自己的理解，我对某些算法语句做了注释，并在证明中对某些部分添加了一点辅助性文字，希望读者能较准确地理解证明的正确性。
对读者的建议：
. 具备离散数学、图论、数据结构以及算法设计与分析等相关课程的知识。
. 按照“问题描述–求解算法–算法性能 (证明)”的思路来阅读。
– 若你计划精读此书，则在未完全理解某环节时，最好不要阅读后面的内容，以免失去阅读和理解的兴趣。当你克服了所遇到的阅读困难时，会有收获的喜悦。
– 若你打算泛读此书，只希望了解网络流算法的基本思想及其性能，则可仔细阅读“问题描述”和“算法描述”，暂可适当忽略有关证明的文字。
感谢同事乔海燕先生的推荐和曲熠编辑的信任，使我有缘翻译此书。翻译中遇到一些特定词语时，有幸咨询老同学黄志毅先生 (移居新西兰) 和同事刘咏梅女士 (加拿大籍)，他们对我的求助都给予了及时答复和非常合适的建议，这使我对译文更有信心。对有些用词，有幸咨询学校图书馆的陈璇老师，她的帮助使译文更加通顺。在此，对他们表示衷心感谢。
感谢学生刘顺平所做的辅助工作，他初译了“前言”“致谢”和“练习”等，并完成了参考文献的整理。这些辅助工作无疑加快了本书的翻译进度。
感谢苦难，它使人坚强；感谢生活，它使人豁达；感谢人生，它使人感恩。
在提交译稿前，我多次对照式地阅读译文并努力兼顾原文和顺畅译文。虽已尽吾所能，但无奈知识储备有限，译文难免会出现偏差或误译。在此，敬请广大读者批评、指教！

译者
2021 年 10 月

译者序
前言
致谢
第 1 章 预备知识：最短路径算法 1
1.1 无负权边：Dijkstra 算法 2
1.2 有负权边：Bellman-Ford算法 5
1.3 负权回路的检测算法 9
练习 16
章节后记 17
第 2 章 最大流算法 19
2.1 最优化条件 21
2.2 应用：汽车共享问题 27
2.3 应用：棒球队淘汰问题 28
2.4 应用：最密子图问题 33
2.5 最大改进增广路径算法 37
2.6 容量度量算法 40
2.7 最短增广路径算法 42
2.8 推送–重标算法 44
练习 54
章节后记 59
第 3 章 全局最小割集算法 61
3.1 Hao-Orlin 算法 62
3.2 MA 序算法 68
3.3 随机合并算法 72
3.4 Gomory-Hu 树 76
练习 83
章节后记 85
第 4 章 其他最大流算法 88
4.1 阻塞流算法 88
4.2 单位容量图的阻塞流 90
4.3 Goldberg-Rao 算法 92
练习 96
章节后记 97
版权声明 97
第 5 章 最小代价环流算法 99
5.1 最优化条件 101
5.2 Wallacher 算法 104
5.3 最小均值回路消去算法 109
5.4 容量度量算法 115
5.5 逐次逼近 119
5.6 网络单纯形 124
5.7 应用: 带时限的最大流问题 126
练习 130
章节后记 136
第 6 章 广义流算法 139
6.1 最优化条件 141
6.2 Wallacher 式 GAP 消去算法 146
6.3 负代价 GAP 检测 151
6.4 有损图、Truemper 算法和收益度量 155
6.5 误差度量 161
练习 163
章节后记 164
第 7 章 多物流算法 166
7.1 最优化条件 166
7.2 双物流问题 168
7.3 预备知识：乘权算法 171
7.4 Garg-K.nemann 算法 175
7.5 Awerbuch-Leighton 算法 178
练习 184
章节后记 185
第 8 章 电流算法 187
8.1 最优化条件 187
8.2 无向图的最大流问题 196
8.3 图的稀疏化 199
8.4 简易 Laplacian 求解器 204
练习 210
章节后记 212
版权声明 213
第 9 章 开放问题 214
参考文献 216