403
правки
Изменения
→Схема алгоритма
== Схема алгоритма ==
Для начала проинициализируем предпоток. Пропустим максимально возможный поток по ребрам, инцидентным стоку, увеличив избыточный поток для каждой смежной со стоком вершиной на соответствующую величину. Все остальные потока не несут, следовательно, для вершин не смежных с истоком избыточный поток изначально будет нулевым. Так же для всех вершин, кроме, естественно, истока, установим высоту, равную нулю.
Более формально это можно записать так:
<tex> f(u, v) =
\begin{cases}
c(u, v), & u = s \\
-c(v, u), & v = s \\
0, & u \neq s \text{ and } v \neq s
\end{cases}
</tex>
<tex> h(u) =
\begin{cases}
\left\vert V \right\vert, & u = s \\
0, & u \neq s
\end{cases}
</tex>
== Корректность алгоритма ==
== Оценка быстродействия ==
== Источники ==
