使用 N -1 最大流在无向图中查找全局最小割

Question

我正在尝试实现一种算法，以使用最大流在具有 N 个节点的加权无向图中找到全局最小割。总体思路是固定一个源节点，并将最大流算法（如 Dinic 的算法）从该源节点应用到剩余的 N - 1 个节点中的每一个。

我尝试完全按照这种方式实现该算法，尽管有效，但实现速度很慢。特别是，我注意到实现的瓶颈是在每次运行最大流算法后重置边缘容量。我不知道如何优化它，如果可能的话。有人对如何解决这个问题有任何想法吗？

Answer 1

您可以使用 Stoer–Wagner 算法来查找全局最小割，而不是为

t

的每个可能值查找最小 s-t 割。