Часть 5. Алгоритмы на графах. На этом рисунке показаны транспортные сети (слева) и остаточные сети (справа) для каждого этапа алгоритма выталкивания превосходящего потока на базе очереди

РИСУНОК 22.28. ОСТАТОЧНАЯ СЕТЬ (ОЧЕРЕДЬ FIFO ДЛЯ ВЫТАЛКИВАНИЯ ИЗБЫТОЧНОГО ПОТОКА)

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

Глава 22. Потоки в сетях

9 8 7 6 5 4 3____

РИСУНОК 22.29. ХУДШИЙ СЛУЧАЙ ВЫПОЛНЕНИЯ АЛГОРИТМОМ ВЫТАЛКИВАНИЯ ИЗБЫТОЧНОГО ПОТОКА, ПОСТРОЕННОГО НА БАЗЕ ОЧЕРЕДИ FIFO

Данная сеть представляет семейство сетей с V вершинами, таких, что общее время прогона алгоритма выталкивания избыточного потока пропорционально V². Она состоит ребра с пропускной способностью, равной единице, исходящих из истока (вершина 0) и горизонтальных ребер с пропускной способностью v - 2, ведущих слева направо в сток (вершина 10). На начальном этапе алгоритма выталкивания избыточного потока (сверху) мы выталкиваем одну единицу потока из каждого ребра, идущего из истока, в результате чего все вершины становятся активными, за исключением истока и стока. В стандартном представлении графа в виде списков смежных вершин они попадают в очередь FIFO активных вершин в обратном порядке, как показано в строке под диаграммой сети. На втором этапе (в центре) мы выталкиваем единицу потока из вершины 9 в 10, переводя 9 в неактивное состояние (временно), затем выталкиваем единицу потока из вершины 7 в 8, переводя 8 в активное состояние и т.д. Только вершина 1 остается неактивной. На третьем этапе (внизу) мы проходим через аналогичный процесс, чтобы сделать вершину 2 неактивной. Этот процесс продолжается на протяжении V — 2 этапов.

Следует отметить, что границы худшего случая дают заниженную оценку, и в силу этого обстоятельства не всегда годятся для прогнозирования производительности алгоритма на реальных сетях (хотя расхождение между ними не настолько велико, какое мы находим в случае алгоритмов определения аугментальных путей). Например, алгоритм FIFO нахо­дит поток в сети, представленной на рис. 22.30 за 15 этапов, в то время как оценка, по­лученная на основании свойства 22.13, утверждает, что число этапов для его вычисления не превышает 182.

Чтобы повысить производительность, мы можем попытаться использовать в програм­ме 22.5 стек, рандомизированную очередь или любой другой вид обобщенной очереди. Один из подходов, хорошо зарекомендовавших себя на практике, заключается в такой реализации обобщенной очереди, чтобы функция могла GQGet возвращать максималь­ную активную вершину.

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

РИСУНОК 22.30. АЛГОРИТМ ВЫТАЛКИВАНИЯ ПРЕВОСХОДЯЩЕГО ПОТОКА (С ОЧЕРЕДЬЮ FIFO)

Приведенная последователь­ность диаграмм показывает, как реализация метода выталкивания превосходящего потока находит максималь­ный поток на демонстрацион­ном примере сети. Он выполняет обработку в несколько этапов. Сначала он проталкивает максимально возможную величину потока из истока по исходящим из него ребрам (диаграмма слева вверху). Затем выполняется проталкивание потока из каждого такого узла и продолжение этой процедуры до тех пор, пока все узлы не придут в равновесие.