Глава 22, Потоки в сетях. int cap() const { return pcap; } int flow() const { return pflow; } bool from (int v) const

int cap() const { return pcap; } int flow() const { return pflow; } bool from (int v) const

{ return pv == v; } int other (int v) const

{ return from(v)? pw: pv; } int capRto(int v) const

{ return from(v)? pflow: pcap - pflow; } void addflowRto(int v, int d)

{ pflow += from(v)? -d: d; } };

Остаточные сети позволяют нам использовать любой обобщенный поиск на графе (см. раздел 18.8) для поиска аугментального пути, поскольку любой путь из истока в сток в остаточной сети непосредственно соответствует аугментальному пути в исходной сети. Увеличение потока вдоль этого пути приводит к изменениям в остаточной сети: напри­мер, по меньшей мере, одно ребро в остаточной сети меняет направление или исчезает (однако практикуемый нами способ абстрактной остаточной сети означает, что мы про­сто проводим проверку с целью отыскания положительной пропускной способности, и фактически нам не нужно вставлять и удалять ребра). На рис. 22.16 в качестве примера показана последовательность аугментальных путей и соответствующие остаточные сети.

Программа 22.3 представляет собой реализацию, построенную на базе очереди с при­оритетами, которая охватывает все эти возможности, используя для этой цели слегка мо­дифицированную версию полученной нами реализации поиска по приоритету на графах из программы 21.1, которая показана в программе 22.4. Эта реализация позволяет выби­рать нужную реализацию алгоритма Форда-Фалкерсона из нескольких различных клас­сических реализаций этого алгоритма за счет простого выбора приоритетов, который обеспечивает реализацию различных структур данных для бахромы.

Как было показано в разделе 21.2, использование очереди с приоритетами для реали­зации стека, очереди или рандомизированной очереди для структуры данных типа бахрома влечет употребление дополнительного множителя lgV, учитывающего затраты на опера­ции с бахромой. Ввиду того, что мы можем избежать этих затрат, воспользовавшись АТД обобщенной очереди в реализациях, подобных программе 18.10 с прямыми реализация­ми, мы полагаем при анализе алгоритмов, что затраты на операции с бахромой в рассмат­риваемых случаях постоянны. Используя единственную реализацию программы 22.3, мы тем самым подчеркиваем наличие прямой связи между различными реализациями алго­ритма Форда-Фалкерсона.

Несмотря на свою универсальность, программа 22.3 не охватывает всех реализаций алгоритма Форда-Фалкерсона (см. например, упражнения 22.36 и 22.38). Исследователи продолжают разрабатывать новые пути реализации этого алгоритма. Однако семейство алгоритмов, охватываемых программой 22.3, получило широкое распространение, и оно служит нам основой для понимания вычислений максимальных потоков и знакомит с ре­ализациями, которые хорошо зарекомендовали себя в практических сетях.

Часть 5. Алгоритмы на графах

РИСУНОК 22.16. ОСТАТОЧНЫЕ СЕТИ (АУГМЕНТАЛЬНЫЕ ПУТИ)

Вычисление аугментальных путей в транспортной сети эквивалентно поиску ориентиро­ванных путей в остаточной сети, определяемой потоком. Для каждого ребра в исходной транспортной сети мы создаем в остаточной сети ребро в каждом направлении: одно в направлении потока с весом, равным неисполь­зованной пропускной способнос­ти, а другое - в обратном направлении с весом, равным потоку. Ни в одном из случаев мы не включаем в сеть ребра, вес которых равен 0. Первоначально (диаграмма вверху) остаточная сеть ничем не отличается от транспортной сети с весами ребер, равными их пропускным способностям. Когда мы произво­дим наращивание потока вдоль пути 0-1-3-5 (вторая диаграмма сверху), мы заполняем ребра 0-1 и 3-5 до их пропускной способности с таким расчетом, чтобы они поменяли направление в остаточ­ной сети, мы уменьшаем вес ребра 1-3 с тем, чтобы он соответствовал оставшемуся потоку, и добавляем ребро 3-1 с весом 2. Аналогично, когда мы производим наращивание вдоль пути 0-2-4-5, мы заполняем ребро 2-4 до его пропускной способнос­ти, так что оно меняет направ­ление на обратное, и получаем ребра, ведущие в разных направле­ниях между вершинами 0 и 2 и между вершинами 4 и 5, пред­ставляющие поток и неиспользо­ванную пропускной способность. После того, как будет проведено наращивание потока вдоль пути 0-2-3-1-4-5 (диаграмма внизу), в остаточной сети не остается ни одного ориентированного пути из истока в сток, в связи с чем отсутствуют аугментальные пути.