Этот вопрос касается временной сложности алгоритма максимального потока Форда-Фулкерсона при использовании DFS для поиска путей расширения.
Существует хорошо известный пример, показывающий, что при использовании DFS может потребоваться линейное число итераций в максимальном потоке, см., Например, страницу Википедии, на которую ссылается выше.
Тем не менее, я не совсем уверен в этом примере: стандартная реализация DFS не будет демонстрировать поведение чередования между B и C в качестве первого узла пути (с использованием имен вершин со страницы Википедии).
Итак, давайте введем очень естественное условие, что всякий раз, когда DFS посещает узел , он всегда проверяет соседей в одном том же порядке. Есть ли еще примеры, для которых FF с DFS использует большое количество итераций?у
Как вариант, предположим, что у нас есть дополнительное свойство, заключающееся в том, что различные порядки соседей соответствуют некоторому произвольному, но фиксированному глобальному упорядочению вершин. Это имеет значение?
Это кажется мне довольно простым вопросом; Я заранее прошу прощения, если ответ хорошо известен, но я не эксперт по потокам, и некоторые поиски в Google ничего не нашли.
Изменить: Ответ оказывается да, есть еще примеры. Смотрите рисунок 2 этой статьи . В этих примерах FF с DFS принимают экспоненциальное (по числу вершин) количество итераций. Кажется, легко доказать, что это тесно, т. Е. Что число итераций всегда ограничено (независимо от значений емкостей).
источник
Ответы:
Если списки смежности фиксированы заранее, то DFS всегда завершается (даже если есть нерациональные возможности).
См. Dean, Goemans, Immorlica - Конечное завершение алгоритмов «дополнения пути» в присутствии данных иррациональной проблемы .
источник