Изменения
Нет описания правки
Для начала определим для каждой вершины <tex>v</tex> данной сети <tex>G</tex> длину кратчайшего <tex>s \leadsto v</tex> пути из истока и обозначим ее <tex>d[v]</tex> (для этого можно воспользоваться [[Обход в ширину|обходом в ширину]]).
В слоистую сеть включаем только те ребра рёбра <tex>(u,v)</tex> исходной сети, для которых <tex>d[u] + 1 = d[v]</tex>.
Полученная сеть ациклична, и любой <tex>s \leadsto t</tex> путь в слоистой сети является кратчайшим путём в исходной, из свойств обхода в ширину.
[[Файл:Слоистая_сеть.png|500px |thumb|center| Слоистая сеть с пятью слоями. <tex>s = 0, t = 6</tex>]]
В примере ребрарёбра, обозначенные пунктиром, не входят в слоистую сеть.
Слоистую сеть для графа G будем называть '''вспомогательной сетью'''.
<tex>f[u][v]</tex> {{---}} поток через ребро <tex>(uv)</tex>.
<tex>p[u]</tex> {{---}} [[Алгоритм_поиска_блокирующего_потока_в_ациклической_сети#.D0.A3.D0.B4.D0.B0.D0.BB.D1.8F.D1.8E.D1.89.D0.B8.D0.B9_.D0.BE.D0.B1.D1.85.D0.BE.D0.B4 | номер первого неудаленного неудалённого ребра идущего из u]]
'''bool''' bfs():
delta = dfs(v, min(minC, c[u][v] - f[u][v]))
'''if''' delta != 0
f[u][v] += delta <font color="darkgreen">// насыщаем ребра рёбра по пути dfs</font>
f[v][u] -= delta
'''return''' delta
