我正在寻找一种算法，当给定的两个节点“s”和“t”在无向图中时，找到最小切割边，将图划分为两个 A 和 B，“s”将在 A 中B 中的“t”将。
我看到大多数人建议使用 Ford–Fulkerson 算法来完成该任务，地址为 here 。我在想是否可以使用 Dinic 的算法来实现。由于 Dinic 算法可以通过动态树来加速。因为我想以最快的方式找到最小切割边缘。
哪种算法可以更快地在巨大的无向图中找到最小割边？
在研究这些算法的细节时，我想听听一些建议。
提前致谢
最佳答案
基本上，任何解决最大流的算法，也解决最小割。获得流量后，找到 residual flow graph 。在此图中，运行 BFS来自来源s。最小切割只是边集 (u, v)，其中 u 可从 s 到达，并且 v 不是。
自 Dinic仅为 O(V2E)，而不是 FF 的 θ(E2V)，那么它将一般来说，速度更快。
在这种情况下，查找残差流图和运行 BFS 的成本可以忽略不计。
关于algorithm - 如何使用Dinic算法找到无向图中的最小割边？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/36054690/