algorithm - 福特富尔克森..后缘的目的是什么？

Question

我正在学习 Ford Fulkerson 算法，我对后向边缘的目的以及它们如何帮助我们达到最大流量感到困惑。我看过几个不同的视频并阅读了一些关于算法的文档，但没有任何点击。也许这里有人可以用对我来说有意义的方式来表达它！

Answer 1

Gassa's comment is correct. Here is a simple example.

Suppose you have a source S, a sink T, and two intermediate nodes A and B, and paths from S to A and A to T, and from S to B and B to T of capacity 1.

  A
 / \
S   T
 \ /
  B

Obviously there is a flow of weight 2 using each edge. Now, add an edge from A to B of capacity 1.

  A
 /|\
S V T
 \|/
  B

This doesn't increase the maximum flow, but it gives you a chance to mess up when you create a flow incrementally. You could start with S->A->B->T.

  A
 /|
S V T
  |/
  B

In order to find the maximum flow, you need to be able to decrease the flow from A to B. You can do this by increasing the flow along S->B->A->T.

  A         A         A
 /|         |\       / \
S V T  +  S ^ T  =  S   T
  |/       \|        \ /
  B         B         B

Going backwards along A->B means you decrease the flow from A to B.