Изменения

Пусть дана [[Определение_сети,_потока#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D0.B5_.D1.81.D0.B5.D1.82.D0.B8|сеть]] <tex> G </tex>, все ребра рёбра которой имеют целочисленную [[Определение_сети,_потока#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D0.B5_.D1.81.D0.B5.D1.82.D0.B8|пропускную способность]]. Обозначим за <tex> U </tex> максимальную пропускную способность: <tex> U = \max\limits_{(u, v) \in E} c(u, v), \Delta = 2^{\lfloor\log_2U\rfloor} </tex>. Обозначим количество вершин за <tex> n </tex>, а количество ребер за <tex> m </tex>.

Идея алгоритма заключается в нахождении путей с высокой пропускной способностью в первую очередь, чтобы сразу сильно увеличивать [[Определение_сети,_потока#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BF.D0.BE.D1.82.D0.BE.D0.BA.D0.B0|поток ]] по ним, а затем по всем остальным. Для этого воспользуемся масштабом <tex> \Delta </tex>. Изначально положим <tex> \Delta = 2^{\lfloor \log_2 U \rfloor} </tex>.

На каждой итерации найдем увеличивающие пути в [[Дополняющая_сеть,_дополняющий_путь|дополняющей сети ]] алгоритм находит [[Дополняющая_сеть,_дополняющий_путь|дополняющие пути]] с пропускной способностью, не меньшей <tex> \Delta </tex>, и увеличим увеличивает поток вдоль них.Уменьшив масштаб <tex> \Delta </tex> в <tex> 2 </tex> раза, переходит к следующей итерации. Очевидно, что при <tex> \Delta = 1 </tex> алгоритм вырождается в алгоритм [[Алоритм_Эдмондса-Карпа|Эдмондса-Карпа]], вследствие чего является корректным. Количество необходимых увеличений путей, основанных на кратчайших путях, может быть много больше количества увеличений, основанных на путях с высокой пропускной способностью.{|border="0" cellpadding="5" width=30% align=center|[[Файл:Flow_scale_1.png|550px|thumb|center|Выбор дополняющих путей в порядке длины]]|[[Файл:Flow_scale_2.png|550px|thumb|center|Выбор пути с высокой пропускной способностью в первую очередь]]|}

Максимальный поток в сети <tex> G </tex> ограничен сверху значением <tex> |f_k| + 2^k m E </tex>, где <tex> |f_k| </tex> {{- --}} значение потокапри масштабе <tex> \Delta = 2^k </tex>.

Количество Суммарное количество увеличивающих путей на <tex> k </tex>{{---ом уровне не превосходит }} <tex> 2m O(E \log U) </tex>.

Следует из предыдущей леммы. Каждый увеличивающий На некоторой итерации алгоритма каждый дополняющий путь на имеет пропускную способность не меньше <tex> 2^k </tex>-ом уровне имеет пропускную способность не меньше .Дополняющий поток на предыдущем шаге ограничен значением <tex> 2^{k + 1} E </tex>. Следовательно, на каждой итерации количество дополняющих путей не превосходит <tex> 2E </tex>.}} {{Лемма|about=3Утверждение

Количество увеличивающих путей не превышает Время работы алгоритма {{---}} <tex> O(m logUE^2 \log U) </tex>.

Следует из предыдущей леммы и фактаВ ходе выполнения алгоритма масштаб <tex> \Delta </tex> принимает следующие значения: <tex> S = \{2^{\lfloor \log_2 U \rfloor}, \ldots, 2^k, \ldots, 2, 1, что 0\} </tex>. Тогда <tex> |S| = O(\log U) </tex> {{---}} количество уровней итераций алгоритма. Количество итераций алгоритма {{---}} <tex> log_2U O(\log U) </tex>., значит, суммарное количество увеличивающих путей {{---}}<tex> O(E \log U) </tex>.

Алгоритм [[Обход_в_ширину|обхода в ширину]] находит каждый дополняющий путь за время <tex> O(E) </tex>. Следовательно, суммарное время работы алгоритма {{---}} <tex> O(E^2 \log U) </tex>.}}

'''Max_Flow_By_Scalingfunction''' maxFlowByScaling(G: '''graph''',s: '''int''',t: '''int'''): '''int''' '''int''' flow = 0 <texfont color=darkgreen>f \leftarrow 0// поток в сети </texfont> '''int''' scale = <tex>\Delta \leftarrow 2^{\lfloor\log_2U\rfloor}</tex> <font color=darkgreen> // текущий минимальный размер потока, который пытаемся пустить </font> '''while''' scale <tex>\Delta \geq 1geqslant </tex>1 '''do while''' в <tex>G_f</tex> существует увеличивающий путь <tex>s-tp </tex> с пропускной способностью не меньшей <tex>\Delta</tex>меньше, чем scale '''doint''' minCapacity = <tex>P\leftarrow</tex> путь с пропускной способностью не меньшей <tex>\Delta</tex> <tex>\delta \leftarrow \min\{c_{ij}c(u, v) \colon(iu,jv)\in Pp\}</tex> <font color=darkgreen> // минимальная пропускная способность в увеличивающем пути </font> увеличить поток по рёбрам <tex>Pp </tex> на <tex>\delta</tex>minCapacity обновить <tex>G_f</tex> <tex>f \leftarrow f flow = flow + \delta</tex>minCapacity <tex>\Delta \leftarrow \Delta scale = scale / 2</tex> '''return''' <tex>f</tex>flow == См. также ==* [[Определение_сети,_потока|Определение сети, потока]]* [[Алоритм_Эдмондса-Карпа|Алоритм Эдмондса-Карпа]]* [[Алгоритм_Форда-Фалкерсона,_реализация_с_помощью_поиска_в_глубину|Алгоритм Форда-Фалкерсона]]

== Литература Источники информации ==

* [http://wwwlogic.cs-seminarpdmi.spbras.ru/reportsics/34talks/21stream.pdf ''Андрей Станкевич'': Задача о максимальном потоке]* [https://youtu.be/sEwp5ZAJJps?t=18m9s ''Андрей Станкевич'': Лекториум, дополнительные главы алгоритмов, лекция 12]