Я читал об упражнении в книге по алгоритмам. Одно из упражнений: для данной сети потоков G=(s,t,V,E,U), где s - единственный источник, t - единственная цель, V - набор вершин, E - набор ребер (предполагается, что он направлен), и U - установленная емкость (предполагается, что неотрицательные целые числа) дают алгоритм для всех ребер (i,j) увеличения максимального расхода, если их емкость установлена в бесконечность (емкости других ребер остаются неизменными, конечно).
Пусть m будет числом ребер и n числом вершин.
Самый наивный алгоритм - изменить емкость (i,j), а затем запустите Ford-Fulkerson и сравните новое значение потока. Этот алгоритм имеет сложность O (m ^ 3 n), предполагая, что мы принимаем реализацию Форда-Фулкерсона со сложностью O (m ^ 2 n).
Мое улучшение состоит в том, чтобы рассмотреть это:
Запустите Ford-Fulkerson на исходном графике G и получите максимальный поток x.
Получите остаточную сеть G(x). Найдите множество всех вершин S, к которым мы можем прийти из s (конечно, по пути с ненулевой емкостью).
Для каждого ребра (i,j), если i=s и j=t, ответ - бесконечность; если i и j находятся одновременно в S или нет в S, ответ равен нулю; в противном случае мы повторно запустим Ford-Fulkerson в новой сети с измененными мощностями.
Обратите внимание, что улучшение в основном выполняется на шаге 3 и является улучшением, только если число ребер, соединяющих S и V\S мало. Для некоторых конкретных графиков сложность асимптотики c такая же, как и у простого алгоритма, описанного выше.
Есть ли лучшее улучшение?