5.4 动态规划：寻找最短路径的有效方法

    编辑距离是动态规划很好的应用，用O(n^2)的时间复杂度解决了指数难度的问题。

主干网的建设

    因为光纤上下水平移动，可有两结论：

    1）当直线在所有点上方，向下平移时，N个点到直线的距离之和是越来越小

    2）当直线在所有点下方，向下平移时，N个点到直线的距离之和是越来越大

    而当直线上方点的个数小于下方点的个数时，直线继续下移导致其上方点到其距离之和的增加小于其下方点到其距离之和的减少，因此当直线上下点的数量一致（N/2）时，直线继续下移导致上方点距离的增加和下方点距离的减少相互抵消，此时的一段区间都可以放置光纤。

    当然，这是在N为偶数的情况下。若N为奇数，使所有点向垂直坐标系投影后，取中间的那一点，穿过这一点的直线即为所求。

    总结：动态规划的问题很多都很巧妙，著名的Dijkstra算法也是其中之一，详情可见这个B站视频：11-3: Dijkstra 算法 寻找有权图中最短路

5.5 最大流：解决交通问题的方法

    如图，求从S到T的最大流量，可以将S和T置于两个不同组中，组间进行切割，L1～L4是不同的切割方式，其中L2是所有切割方式中的最小切割（Minimum S-T cut），也是整个网络S到T的最大流（Maximum flow）：8+3+4+9=24。

    从任意初始流量分布开始，如果系统中S到T还未到达最小割（或最大流），可以证明能够不断找到一条从 S -> T 的流量可以增加的增广路径（Augmenting Path）

    可以看出，在最小割L2上的边的流量都已经饱和了，因此该有向连通图的流量不可能再增加了。该算法即为Ford-Fulkerson Algorithm，见伪代码（或系列视频：13-1: 网络流问题基础 Network Flow Problems）：

    对于有权图G=(V,E)，如果(u,v)属于E，它的权重为capacity(u,v)，表示该边容量。需要另一个数组flow(u,v)，表示每条边已分配的流量（初始化为0）。此外还需要一个临时数组remaining(u,v)，表示每条边还剩余可分配的流量。由remaining这个数组和节点的集合构成一个剩余流量图Gr。如果u,v之间没有剩余流量了，则(u,v)这条原属于图G的边，就不在Gr中。

    福特-富尔克森（Ford-Fulkerson）算法的优点是，当网络中各边容量相近时，收敛快。但当存在边容量相差好几个数量级时，收敛慢。基于此，改进算法埃德蒙兹-卡普（Edmonds-Karp）算法可以解决，因为其时间复杂度与各边容量无关。

5.6 最大配对-流量问题的扩展

    在二分图的配对应用中，往往我们需要达到最大配对，比如婚恋配对最多或者网约车司机和乘客配对最大，这样可以利益最大化：

    可以使用前面所说的最大流-最小割来解决该问题，只要认为添加源点S和终点T即可，边的最大容量和最小容量都是1，那么有几对能匹配，最大流量就是几：

    此外，《算法导论》中，还有介绍针对二分图配对时增广路径的“交替路径”方法。