Алгоритм масштабирования потока
Алгоритм
Пусть дана сеть , все ребра которой имеют целочисленную пропускную способность. Обозначим за максимальную пропускную способность: .
Идея алгоритма заключается в нахождении путей с высокой пропускной способностью в первую очередь, чтобы сразу сильно увеличивать поток по ним, а затем по всем остальным. Для этого воспользуемся масштабом . Изначально положим .
На каждой итерации в дополняющей сети алгоритм находит дополняющие пути с пропускной способностью не меньшей и увеличивает поток вдоль них. Уменьшив масштаб в раза, переходит к следующей итерации.
Очевидно, что при Эдмондса-Карпа, вследствие чего является корректным.
алгоритм вырождается в алгоритмКоличество необходимых увеличений путей, основанных на кратчайших путях, может быть много больше количества увеличений, основанных на путях с высокой пропускной способностью.
Оценка времени работы
Лемма (1): |
Максимальный поток в сети ограничен сверху значением , где — значение потока при масштабе . |
Доказательство: |
В конце итерации с масштабом разрез . , сеть может быть разбита на два непересекающихся множества и так, что остаточная пропускная способность каждого ребра, идущего из в , не превосходит масштаба . То есть образуетсяПри этом, количество таких ребер не превосходит Значит, значение остаточного потока не может превосходить . . |
Лемма (2): |
Суммарное количество увеличивающих путей — . |
Доказательство: |
На некоторой итерации алгоритма каждый дополняющий путь имеет пропускную способность не меньше Дополняющий поток на предыдущем шаге ограничен значением . . Следовательно, на каждой итерации количество дополняющих путей не превосходит . |
Утверждение: |
Время работы алгоритма — . |
В ходе выполнения алгоритма масштаб принимает следующие значения: . Тогда — количество итераций алгоритма.Количество итераций алгоритма — Алгоритм , значит, суммарное количество увеличивающих путей — . обхода в ширину находит каждый дополняющий путь за время . Следовательно, суммарное время работы алгоритма — . |
Псевдокод
Max_Flow_By_Scaling(G,s,t)while do while в существует увеличивающий путь с пропускной способностью не меньшей do увеличить поток по рёбрам на обновить return