322
правки
Изменения
→Используемые определения
#[[Блокирующий поток]]
#Вспомогательная (слоистая) сеть.
::Для начала определим для каждой вершины <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> путь во вспомогательной сети является кратчайшим путём в исходной.
