给定一个带有源 s 和汇 t 的流网络。对于每两个节点u，v，假设从u到v的容量与从v到u的容量相同。给定两个顶点 x、y，设计一个多项式时间算法来找到从 x 到 y 的一条路径，您可以沿着该路径发送尽可能多的流量。 简要论证算法的正确性并分析运行时间。
非常感谢
最佳答案
您面临的问题称为最大流算法，它有多个 solutions , 它们都是多项式的。
你可以使用 Ford–Fulkerson algorithm ，因为它很容易理解，而且正如您所见，wiki 页面包含您想要的关于该算法的所有内容。
编辑:我之前提供的答案并没有给你单一的路径，而是给你最大的流量。
要找到单一路径，您只需在 x 和 y 之间的每条路径中找到瓶颈。瓶颈是指路径中容量最低的边缘，因为路径的容量就是该边缘的容量。
要找到每条路径中的最低容量，您可以简单地开始从图中从最低容量到最高容量移除边，并且从图中移除每条边只需检查 x 和 y 是否连接。使 x 和 y 断开连接的第一条边是您想要的边，它的容量就是您想要的容量。因为 x 和 y 之间的每条路径要么有这条边，要么有一条容量较低的边。
算法的时间复杂度:
- 排序边:O(E log E)。
- 删除每条边，直到找到所需的边:O(E)。
- 检查第二步的连通性:O(V + E)(使用 Strongly connected component 算法检查)
所以算法的复杂度是:O(E log E) + O(E V + E2) = O(E V + E2)
关于algorithm - 具有源 S 和汇 T 的流网络，如何找到任意 2 个顶点之间的最大流？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/27590749/