如何使用 Dinic 算法在无向图中找到最小割边？
how to use Dinic's algorithm to find min-cut edges in undireted graph?
我正在寻找一种算法，当给定两个节点 's' 和 't' 在无向图中，找到最小切割边，将图划分为两个 A 和 B， 's' 会在 A 中，'t' 会在 B 中。
我看到大多数人建议使用 Ford–Fulkerson 算法来完成该任务，here。我在想是否可以使用 Dinic 的算法。由于 Dinic 的算法可以用动态树加速。因为我想以最快的方式找到最小切割边缘。
哪种算法在巨大的无向图中找到最小割边更快？
在研究这些算法的细节时，我想听听一些建议。
提前致谢
基本上，任何求解最大流的算法也都求解最小割。获得流程后，从来源 s 中找到 residual flow graph. In this graph, run BFS。最小切割只是边的集合 (u, v) 可以从 s[=27= 到达 u ]，而 v 不是。
因为 Dinic 只是 O(V2E) 而不是 FF 的 Θ( E2V)，那么会快一些，一般来说。
在这种情况下，查找残差流图和 运行 BFS 的成本可以忽略不计。
我正在寻找一种算法，当给定两个节点 's' 和 't' 在无向图中，找到最小切割边，将图划分为两个 A 和 B， 's' 会在 A 中，'t' 会在 B 中。
我看到大多数人建议使用 Ford–Fulkerson 算法来完成该任务，here。我在想是否可以使用 Dinic 的算法。由于 Dinic 的算法可以用动态树加速。因为我想以最快的方式找到最小切割边缘。
哪种算法在巨大的无向图中找到最小割边更快？
在研究这些算法的细节时，我想听听一些建议。
提前致谢
基本上，任何求解最大流的算法也都求解最小割。获得流程后，从来源 s 中找到 residual flow graph. In this graph, run BFS。最小切割只是边的集合 (u, v) 可以从 s[=27= 到达 u ]，而 v 不是。
因为 Dinic 只是 O(V2E) 而不是 FF 的 Θ( E2V)，那么会快一些，一般来说。
在这种情况下，查找残差流图和 运行 BFS 的成本可以忽略不计。