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

---作者简介---
大卫·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的主编。

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

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