数据结构中MaxFlow问题的路径选择是否有限制？

Question

在下面的最大流问题中，算法首先可以选择S-A-D-T路径。在这种情况下，算法将不再看到任何增强路径，因此它将生成4作为最大流的答案。但是，如果算法首先选择任何其他路径，则会看到最大流变为5。

​

​

Answer 1

您似乎没有注意到，Ford-Fulkerson算法以两种方式更新了残差图：

1. 从所选路径的所有边缘减去路径流
2. 添加沿着所选路径

反向边缘的路径流

因此，在您使用flow 3选择了3路径之后，残差图现在将包含一个带有flow 2的增强路径S-B-D-A-C-T，从而达到5的总流。沿相反边缘的流只会取消现有的流，因此只有2的流才会从A保持到D。