Как использовать алгоритм Диникова для поиска краев с минимальным разрезом в нулевом графике?

Question

Я ищу алгоритм, когда заданные два узла 's' и 't' в объявленном графе, чтобы найти грани с минимальным разрезом, который разбивает граф на два A и B, 's' будет в A и 't' будет в B.

Я вижу большинство людей, предлагающих для алгоритма Форда-Фулкерсона для этой задачи, по адресу here. Я думаю, что можно использовать алгоритм Динина для этого. Поскольку алгоритм Dinic может ускоряться с динамическим деревом. Потому что я хочу найти минимально разрезанные края самым быстрым способом.

Какой алгоритм быстрее подходит для поиска минимальных границ в огромном неориентированном графе?

Я хотел бы услышать некоторые советы, пока я изучаю детали этого алгоритма.

Заранее спасибо

Answer 1

В принципе, любой алгоритм, который решает максимальный поток, решает также минимальный разрез. Когда у вас есть потоки, найдите residual flow graph. На этом графике запустите BFS от источника s. Мин разрез только множество ребер (U, V), для которого у достижима из с и v нет.

Поскольку Dinic только O (V Е), в отличие от ФФ Θ ^{(E 2} V), то это будет быстрее, в общем.

Стоимость поиска остаточного потока и работы BFS в этом случае незначительна.