algorithm - 如何使用 Dinic 算法在无向图中找到最小切边？

Question

我正在寻找一种算法，当一个给定的两个节点's'和't'在一个未处理的图中，找到最小切边，它将图分成两个A和B，'s'将在A和't ' 将在 B.

我看到大多数人建议使用 Ford-Fulkerson 算法来完成这项任务，在这里。我在想是否可以使用 Dinic 的算法。由于 Dinic 的算法可以通过动态树来加速。因为我想以最快的方式找到最小切边。

哪种算法可以更快地在巨大的无向图中找到最小切边？

在研究这些算法的细节时，我想听听一些建议。

提前致谢

Answer 1

基本上，任何解决最大流的算法也解决了最小割。一旦你有了流量，找到剩余流量图。在此图中，从源s运行BFS。最小切割只是一组边(u, v)，其中u可以从s到达，而v不能。

由于Dinic只是O(V ² E)而不是 FF 的Θ(E ² V)，所以它通常会更快。

在这种情况下，查找剩余流图和运行 BFS 的成本可以忽略不计。