如何使用Dinic的算法在無向圖中找到最小切割邊緣？

Question

我正在尋找一個算法，當一個給定的兩個節點的'和'在一個未經過訓練的圖中，找到最小切割邊緣，它將圖形分成兩個A和B'''將在A和「T」將在B.

我看大多數人提示了福特Fulkerson算法，以用於該任務，在here。我在想，可以使用Dinic的算法。由於Dinic的算法可以通過動態樹加快速度。因爲我想以最快的方式找到最小切割邊緣。

哪種算法更快找到一個巨大的無向圖中最小切割邊緣？

我希望聽到一些建議，同時我正在研究這些算法的細節。

預先感謝

Answer 1

基本上，任何算法解決了最大流量，也解決了最小割。一旦你有了流量，找到residual flow graph。在此圖中，從源s運行BFS。最小切割只是一組邊（U，V）爲其Ü是從小號可達的，並且v不是。

Dinic由於僅ø（V E）相對於FF的Θ（E V），那麼這將是較快，一般。

找到殘餘流圖和運行BFS的成本是微不足道的，在這種情況下。