概念

管道网络中每条边的最大通过能力（容量）是有限的，实际流量不超过容量。

最大流问题(maximum flow problem)，一种组合最优化问题，就是要讨论如何充分利用装置的能力，使得运输的流量最大，以取得最好的效果。求最大流的标号算法最早由福特和福克逊于1956年提出，20世纪50年代福特(Ford)、福克逊(Fulkerson)建立的“网络流理论”，是网络应用的重要组成成分。

把最大流算法想象成两个运输站之间运货，两个运输站之间有很多个中转站，每个中转站都有一个最大容量，站与站之间运货都有不同的运货量，而且中转站不会留货物，所以货物的总量一定等于源站的出货数或者汇站的进货数。最大流算法就是在不超过所有中转站的容量的情况下，求最大出货量/进货量以及所有中转站之间的运货量。

案例

下图标出了某地区的运输网，各节点之间的运输能力标记在运输网各端点的连线上（单位：万吨/小时）。请问，从节点①到节点⑥的最大运输能力（流量）可以达到（）万吨/小时？

解析

• 使用标号算法来解决最大流量问题（为了最简化说明算法思路和求解过程，本文不引入一大堆的符号、公式，这样只会让初学者眼花缭乱。）。
• 算法原理简析：
  • 起点（①）和终点（⑥）之间有许多种连线方式，有的经过节点少，有的经过节点多，但无论经过多少节点，每一种线路的最大运输量是取决于该连线中运输量最小的那一段。例如：①②⑤⑥线路，其中最大流量值最低的是①②段，如果要从①运输到⑥，最大流量是6，因为超过6，①②段无法容纳。
  • 标号算法需要在所有线路方案中逐一找出剩余线路方案，找出每种线路方案中最大流量上限值x，作为结果集（该结果集的元素值的和即为最终答案），线路中的每一段连线流量都要扣除x，若扣除x后的流量等于0，则断开剩余流量为0的连线；
  • 不断重复上一步，扩充结果集的同时扣除剩余连线剩余流量，直到起点和终点之间不再有任何连通方案。

  如果看不懂欢迎留言。

步骤

1. 以①为起点，⑥为终点，从运输网中任取一条连通方案，假设选取①②⑤⑥，该线路最大流量上限为6（①②），每段连线的最大流量扣掉6，剩余流量为0的连线断开，表示已经不可再接收流量。此时结果集为{6}。
   
2. 再取一条新线路，假设为①③⑤⑥，最大流量上限为10（①③），同样每段连线扣除10，剩余流量为0的连线，直接断开。此时结果集为{6，10}。
   
   
3. 再次选择线路，①④⑥，最大流量上限为5（④⑥），每段连线扣除5，剩余流量为0的连线，直接断开。此时结果集为{6，10，5}。
   
   
4. 再次选择线路，①④③⑤⑥，最大流量上限为1（④③），每段连线扣除1，剩余流量为0的连线，直接断开。此时结果集为{6，10，5，1}。
   
   
5. 再次选择线路，①④②⑤⑥，最大流量上限为1（④②），每段连线扣除1，剩余流量为0的连线，直接断开。此时结果集为{6，10，5，1，1}。
   
   
6. 从上图中观察到，此时已经没有可连通起点和终点的线路了，所以最终结果集就是{6，10，5，1，1}。其元素值的和为 6+10+5+1+1 = 23。

参考资料

https://blog.csdn.net/weixin_42419611/article/details/105413547

https://baike.baidu.com/item/%E6%9C%80%E5%A4%A7%E6%B5%81%E9%97%AE%E9%A2%98/19144252?fr=aladdin