增强路径究竟是什么？ [英] What exactly is augmenting path?
问题描述
当谈到计算网络流量时，算法设计手册说：
传统的网络流算法基于扩充路径的思想，并反复找到从s到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 an augmenting path?
推荐答案
扩展路径是一个简单的路径 - 不包含循环的路径 - 通过图形，只使用从源到sink的正容量的边。
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屋！
