algorithm - 具有源 S 和汇 T 的流网络，如何找到任意 2 个顶点之间的最大流？

Question

给定一个带有源 s 和汇 t 的流网络。对于每两个节点u，v，假设从u到v的容量与从v到u的容量相同。给定两个顶点 x、y，设计一个多项式时间算法来找到从 x 到 y 的一条路径，您可以沿着该路径发送尽可能多的流量。简要论证算法的正确性并分析运行时间。

非常感谢

Answer 1

您面临的问题称为最大流算法，它有多个 solutions , 它们都是多项式的。

你可以使用 Ford–Fulkerson algorithm ，因为它很容易理解，而且正如您所见，wiki 页面包含您想要的关于该算法的所有内容。

编辑:我之前提供的答案并没有给你单一的路径，而是给你最大的流量。

要找到单一路径，您只需在 x 和 y 之间的每条路径中找到瓶颈。瓶颈是指路径中容量最低的边缘，因为路径的容量就是该边缘的容量。

要找到每条路径中的最低容量，您可以简单地开始从图中从最低容量到最高容量移除边，并且从图中移除每条边只需检查 x 和 y 是否连接。使 x 和 y 断开连接的第一条边是您想要的边，它的容量就是您想要的容量。因为 x 和 y 之间的每条路径要么有这条边，要么有一条容量较低的边。

算法的时间复杂度:

1. 排序边:O(E log E)。
2. 删除每条边，直到找到所需的边:O(E)。
3. 检查第二步的连通性:O(V + E)(使用 Strongly connected component 算法检查)

所以算法的复杂度是:O(E log E) + O(E V + E²) = O(E V + E²)