Jac*_*ale 38 algorithm graph data-structures network-flow
在谈到时computing network flows,算法设计手册说:
传统的网络流算法基于增加路径的想法,并重复地从s到t找到正容量的路径并将其添加到流中.可以证明,当且仅当它不包含增广路径时,通过网络的流是最佳的.
我不明白是什么augmenting paths.我用Google搜索,发现:
但他们都参考了上面的引用.
任何人都可以真的清楚地解释一下是augmenting path什么？
izo*_*ica 47
增强路径是一条简单的路径 - 一条不包含循环的路径 - 通过图形仅使用从源到接收器的正容量边缘.
所以上面的陈述是显而易见的 - 如果你找不到从源到接收器只使用正容量边缘的路径,那么流量就不能增加.
顺便说一下,该陈述的证明并不那么容易.
增加意味着增加 - 做大.在给定的流网络G=(V,E)和流中f,扩充路径p是从剩余网络source s到其中的简单路径.通过定义,我们可能会增加在边缘的流高达容量可增广路的不违反约束,在取的,并是原流通网络.此外,我们可以增加增强路径p中每个边缘上的流量的最大量称为.证明可以在thomas h的算法介绍中找到.cormen等...sink tGfresidual network(u,v)Cf(u,v)(u,v)(v,u)Gresidual capacity of p