148
правок
Изменения
Нет описания правки
== Определение слоистой сети ==
[[Файл:Слоистая_сеть.png|200px 150px |thumb|cental| Слоистая сеть с пятью слоями с истоком в вершине слоямию. s = 0 и стоком в вершине , t = 6]]
Для начала определим для каждой вершины <tex>v</tex> данной сети <tex>G</tex> длину кратчайшего <tex>s \leadsto v</tex> пути из истока и обозначим ее <tex>d[v]</tex> (для этого можно воспользоваться [[Обход в ширину|обходом в ширину]]).<br/> В слоистую сеть включаем только те ребра <tex>(u,v)</tex> исходной сети, для которых <tex>d[u] + 1 = d[v]</tex>.
Полученная сеть ациклична, и любой <tex>s \leadsto t</tex> путь во вспомогательной сети является кратчайшим путём в исходной, из свойств обхода в ширину.
=== Схема алгоритма ===
#Для каждого ребра <tex>(u,v)</tex> данной сети <tex>G</tex> зададим <tex>f(u,v) = 0</tex>.
#Построим вспомогательную сеть <tex>G_L</tex> из [[Дополняющая сеть, дополняющий путь|дополняющей сети ]] <tex>G_f</tex> данного графа <tex>G</tex>. Если <tex>d[t] = \infty</tex>, остановиться и вывести <tex>f</tex>.
#[[Алгоритм поиска блокирующего потока в ациклической сети|Найдем блокирующий поток <tex>f'</tex> в <tex>G_L</tex>.]].
#Дополним поток <tex>f</tex> найденным потоком <tex>f'</tex> и перейдем к шагу 2.
