Реализация алгоритма проталкивания предпотока

Наконец, необходимо кратко обсудить эффективную реализацию этого алгоритма. Несколько простых структур данных позволят эффективно реализовать каждую из операций алгоритма за постоянное время, так что общая реализация алгоритма займет время O(mn) плюс количество ненасыщающих операций push.
Следователь- но, обобщенный алгоритм будет выполняться за время O(mn2), тогда как версия, которая всегда выбирает узел с максимальной высотой, будет выполняться за время O(n3).

Все узлы с избыточным потоком можно объединить в простой список, чтобы выбор узла с избыточным потоком происходил с постоянным временем. Что касается выбора узла с максимальной высотой H за постоянное время, придется действовать более осмотрительно. Для этого мы будем вести связанный список всех узлов с избыточным потоком на каждой возможной высоте. Обратите вни- мание: если узел v изменяет метку или сохраняет положительный избыточный поток после проталкивания, он остается узлом с максимальной высотой H. Следо- вательно, выбирать новый узел после проталкивания нужно только в том случае, когда текущий узел v уже не имеет положительного избыточного потока. Если узел v находился на высоте H, то новый узел на максимальной высоте также будет находиться на высоте H, или если ни один узел на высоте H не имеет избыточного потока, максимальная высота будет равна H - 1, поскольку предыдущая операция push из v протолкнула поток в узел на высоте H - 1.

Теперь предположим, что был выбран узел v и теперь нужно выбрать ребро (v, w) для применения push(f h, v, w) (или relabel(f, h, v), если такого w не суще- ствует). Чтобы иметь возможность быстро выбрать ребро, мы будем использовать представление графа в виде списка смежности. А точнее, для каждого узла v будет вестись связанный список всех возможных ребер, выходящих из v в остаточном графе (как прямых, так и обратных), и с каждым ребром будет храниться его пропускная способность и величина потока. Следует заметить, что в этом случае в структуре данных будут храниться две копии каждого ребра: прямая и обратная. Эти две копии содержат указатели друг на друга, поэтому обновления, выполня- емые с одной копией, будут переноситься на другую копию за время O(1). Ребра, выходящие из узла v, будут выбираться для операций push в порядке их следования в списке узла v. Чтобы упростить этот выбор, мы будем поддерживать для каждого

узла указатель current(v) на последнее ребро в списке, которое рассматривалось для операции push. Следовательно, если ребро v не имеет избыточного потока по- сле насыщающей операции push из узла v, указатель current(v) останется на этом ребре, и это же ребро будет использоваться для следующей операции push из v.

После насыщающей операции push из узла v указатель current(v) перемещается к следующему ребру в списке.

Здесь принципиально то, что после перемещения указателя current(v) от ребра (v, w) операция push не должна повторно применяться к этому ребру, пока не будет изменена метка v.

(7.31) После того, как указатель current(v) переместится от ребра (v, w), при- менение push к этому ребру невозможно, пока не будет изменена метка v.

Доказательство. После перемещения current(v) от ребра (v, w) вполне логично, что операции push не могут применяться к этому ребру. Либо h(w) > h(v), либо ребро не входит в остаточный граф. В первом случае очевидно, что перед применением push к этому ребру необходимо изменить метку v. Во втором случае необходимо применить push к обратному ребру (w, v), чтобы ребро (v, w) снова вошло в оста- точный граф. Однако если применить push к ребру (w, v), то w окажется выше v, а следовательно, метку v необходимо изменить, прежде чем поток можно будет снова проталкивать от v к w. ■

Так как перед изменением метки ребра не нужно снова рассматривать для при- менения push, приходим к следующему результату.

(7.32) Когда указатель current(v) достигает конца списка ребер для v, к узлу v можно применить операцию relabel.

После изменения метки узла v указатель current(v) возвращается к первому ребру в списке, после чего ребра снова рассматриваются в порядке их следования в списке v.

(7.33) Время выполнения алгоритма проталкивания предпотока, реализован- ного с использованием описанных структур данных, равно O(mn) плюс O(1) для каждой ненасыщающей операции push. В частности, обобщенный алгоритм про- талкивания предпотока выполняется за время O(n2m), а версия, в которой всегда выбирается узел с максимальной высотой, выполняется за время O(n3).

Доказательство. Исходный поток и процедура изменения меток настраивают- ся за время O(m). Операции push и relabel (после того, как операция будет выбра- на) реализуются за время O(1). Рассмотрим узел v. Мы знаем, что метка v может быть изменена не более 2n раз на протяжении алгоритма. Рассмотрим общее время, потраченное алгоритмом на поиск правильного ребра для проталкивания потока из узла v между двумя изменениями метки v. Если узел v имеет dv смежных ребер, то согласно (7.32) на перемещение указателя current(v) между последова- тельными изменениями метки v будет потрачено время O(dv). Следовательно, общее время, потраченное на продвижение указателей current, по алгоритму со- ставляет О(∑^t}d,) = О{тп) , как и утверждалось. ■

7.5.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Реализация алгоритма проталкивания предпотока:

  1. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  2. АЛГОРИТМ УДАЧИ
  3. АЛГОРИТМ
  4. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  5. Алгоритм исцеления:
  6. Алгоритм избавления от боли
  7. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  8. Алгоритм обработки результатов.
  9. 2. Специфика и алгоритмы работы с источниками.
  10. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.