11
第5-5课：最大流问题（图文篇）
source link: https://blog.csdn.net/orbit/article/details/108729348
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
原计划这一课是要讲解最小费用最大流问题，但是图文课每一篇如果字数太多会给手机阅读带来困难，加上读者圈朋友的反馈希望多讲一些基础的内容，因此这一课我们降低点难度，只讲最大流问题。最小费用最大流问题，其实也是在最大流问题的基础上加入类似最短路径算法（SPFA）这样的思路，叠加形成算法，最后的总结部分我会简单介绍一下在最大流算法的基础上实现最小费用最大流问题的两种常用方法，但是这一课，我们只讲最大流问题。
网络流和最大流
最大流问题的典型例子有物流配送、输水管路等。比如这个题目：某地区的自来水供应是由地下的水管网路组成，两个地点之间由粗细不一的水管连接，粗水管的输水能力大，细水管的输水能力小，请规划一个合理的水量和管路组合，使得从水源地到目的地能够获得最大的水量。
图（1）输水管路和最大输水量示意图
我们以《算法导论》一书中的图为例来解释一下上面的问题，如图（1-a）所示，假设图中 0 号顶点为水源地，5 号顶点为目的地，每条边都有两个数字描述，斜杠左边的数字是这条管路当前的输水量，斜杠右边的数字是这条管路的水管的容量；图（1-b）是我们选择给每条管路分配的输水量，这样分配的结果是从水源地到目的地的输水量达到最大值 23。那么是不是随便选择一下管路都能获得输水量的最大值呢？当然不是，如果规划的不合理，会造成细水管被撑满，而粗
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK