究竟增加路径是什么?
问题内容:
谈到时computing network flows
,《算法设计手册》说:
传统的网络流量算法基于 增加路径
的想法,并反复查找从s到t的正容量路径,并将其添加到流量中。可以证明,当且仅当它不包含增长路径时,通过网络的流量才是最佳的。
我不明白那是什么augmenting paths
。我用谷歌搜索,发现:
但他们都引用了上面的引用。
谁能真正清楚地说明什么是augmenting path
?
问题答案:
扩充路径是一条简单的路径-不包含循环的路径-仅使用从源到接收器具有正容量的边通过图形。
因此,以上说明很明显-如果找不到从源到汇的仅使用正容量边缘的路径,那么流量就不会增加。
顺便说一句,证明这种说法不是那么容易。