首页 > 代码库 > 网络流之最大流算法
网络流之最大流算法
最大流
网络流的定义:
在一个网络(有流量)中有两个特殊的点,一个是网络的源点(s),流量只出不进,一个是网络的汇点(t),流量只进不出。
最大流:就是求s-->t的最大流量
假设 u,v 两个点,连接这两个点的边为e(u,v);
对于每一条边都有一个实际流量f(u,v),还有一个容量c(u,v),就是这条边上可以通过的最大流量。
当一条边的容量c(u,v)=0,证明这条边是不存在的,
作为一个合格的网络流,必须满足三个条件:
1>每条边的实际流量小于等于容量 f(u,v)<=c(u,v);
2>f(u,v)=-f(v,u);
3>对于不是源点和汇点的点,流入的流量等于流出的流量
如何来求一个网络的最大流:
如图是一个网路流,很明显看出答案是4。
我们要求s-t的流量,我们可以选择这样来求解,我们先从s点出发,找到一条s-t的路径,记录这条路径上那个最小的实际流量,
算法就是我们要找到很多条这样的路径,但这些路径都应该是不同的,所有我们只需要把这多条路径的的最小流量相加 得到就是最大流、
这个寻找s-t的路径也叫做增广路算法
其实这里困难的就是如何保证这些路径是不会相同的 这是涉及到一个概念 就是残留网络
残留网络就是每次利用增广路算法找到这条路径的最小实际流量 minn,我们在原网络中把这条边的容量都减去minn,所以必定这条路径中一定会有流量为0。
所有下次增广的话,就一定不会走原路 因为你的流量有0,走是没有意义的
网络流之最大流算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。