Могут ли быть тупики в алгоритме Форд Фулкерсон? - PullRequest
0 голосов
/ 03 апреля 2020

Можем ли мы удалить те ребра, которые не приводят к снижению t во время DFS в методе ford fulkerson, аналогично тому, что мы делаем в алгоритме dinics? Если нет, приведите пример.

1 Ответ

0 голосов
/ 03 апреля 2020

Понял. Потому что в ford fulkerson мы можем использовать путь расширения через обратный край, чтобы уменьшить поток прямого края, что может сделать передний край пригодным для использования в следующей итерации DFS. Таким образом, удаление края не очень хорошая идея. Принимая во внимание, что в dini c мертвый v не может быть снова использован после того, как он мертв, поскольку нет вероятности того, что поток ребра, удаляющегося от v, будет уменьшен из-за отсутствия обратных ребер.

...