我正在学习Ford Fulkerson算法，但对后边缘的用途以及它们如何帮助我们达到最大流量感到困惑。我看了几个不同的视频，并阅读了有关该算法的一些文档，但是没有点击。也许有人可以以一种对我有意义的方式来表达它！
加萨的评论是正确的。这是一个简单的例子。
假设您有一个源S，一个接收器T，两个中间节点A和B，以及从S到A和A到T，以及从S到B和B到T的容量为1的路径。
A
/ \
S T
\ /
B
显然，每个边都有权重2的流动。现在，从容量1的A到B添加一条边。
A
/|\
S V T
\|/
B
这不会增加最大流量，但是当您逐步创建流量时，它使您有机会弄乱。您可以从S-> A-> B-> T开始。
A
/|
S V T
|/
B
为了找到最大流量，您需要能够将流量从A减小到B。您可以通过沿S-> B-> A-> T增大流量来实现。
A A A
/| |\ / \
S V T + S ^ T = S T
|/ \| \ /
B B B
沿A-> B向后移动意味着您将流量从A减少到B。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句