究竟什么是增广路径? [英] 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.

我不明白什么是增强路径.我用谷歌搜索，发现:

I don't understand what is augmenting paths. I have googled, and found:

• Wolfram 中的增强路径

维基中的流网络

但他们都参考了上面的引用.

but they all reference to the quote above.

谁能真正清楚地解释一下什么是增强路径?

Can anyone please really clearly explain what is an augmenting path?

推荐答案

增广路径是一条简单的路径 - 一条不包含环的路径 - 仅使用从源到汇的具有正容量的边穿过图.

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屋！