图 - 究竟是增广路径？ [英] graph - What exactly is Augmenting Paths?
问题描述
当谈到计算网络流量，href="http://www.algorist.com/">算法设计手册说
When talking about Computing Network Flows, The Algorithm Design Manual says:
传统的网络流算法是基于增广路径，然后反复地寻找从的积极容量到t的路径，并将其添加到流的想法。它可以证明，通过网络流是最佳的，当且仅当它不包含增广路
Traditional network flow algorithms are based on the idea of augmenting paths, and repeatedly finding a path of positive capacity from s to t and adding it to the flow. It can be shown that the flow through a network is optimal if and only if it contains no augmenting path.
我不明白什么是增广路径。我用Google搜索，结果发现：
I don't understand what is augmenting paths. I have googled, and found:
中钨增广路
等。
但他们都提到上面的报价。
But they all reference to the quote above.
任何人都可以请真正清楚地解释什么是增广路径？
Can anyone please really clearly explain what is Augmenting Paths?
感谢
推荐答案
这是增广路径是一个简单的路径 - 不包含循环的路径 - 通过只使用图形从源到汇正容量边缘。所以，上面的语句是莫名其妙显而易见的 - 如果你不能找到从源头上只使用正面能力的边缘，则流量不能增加（由该声明的证据并不是那么容易的方式）的水槽的路径。
An augmenting path is a simple path - a path that does not contain cycles - through the graph using only edges with positive capacity from the source to the sink. So the statement above is somehow obvious - if you can not find a path from the source to the sink that only uses positive capacity edges, then the flow can not be increased(by the way the proof of that statement is not that easy).
这篇关于图 - 究竟是增广路径？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
