Алгоритм FIFO Push Relabel

Алгоритм push-relabel (альтернативно алгоритм pre-flow-push) — это алгоритм вычисления максимальных потоков в потоковой сети. Алгоритмы push-relabel работают более локализованно, чем метод Форда-Фулкерсона. Вместо того, чтобы исследовать всю остаточную сеть, чтобы найти увеличивающий путь, алгоритмы проталкивания-переметки работают с одной вершиной за раз, просматривая только соседей вершины в остаточной сети.

Интуиция

Алгоритм push relabels можно понять с точки зрения потоков жидкости. Все вершины представляют собой соединения труб, а все направленные ребра представляют собой трубы с определенной пропускной способностью. Каждая вершина имеет два специальных свойства. Они содержат резервуар для хранения избыточного потока, а вершина вместе с резервуаром размещается на платформе на определенной высоте.

Мы можем толкать поток только вниз, то есть из вершины на большей высоте в вершину на меньшей высоте. Первоначально источник находится на высоте V (количество вершин), а сток — на высоте 0. Высота всех остальных вершин равна 0 и увеличивается по мере продвижения алгоритма. Во-первых, мы направляем как можно больше потока из источника во все его промежуточные вершины, где он накапливается в их резервуаре.

Теперь все промежуточные вершины источника переполнены. Мы не можем толкать поток вперед, так как они будут располагаться на высоте 0. Чтобы направить поток вперед, мы должны увеличить их высоту на 1.

Процесс продолжается, пока мы не достигнем раковины.

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

Операции

1. Push: операция Push применяется к переполненной вершине, чтобы протолкнуть поток вперед. Алгоритм находит смежные вершины u , которые находятся на более низкой высоте, чем u . Для каждой такой соседней вершины он отправляет максимально возможный поток, который является минимумом избыточного потока в u и пропускной способности ребра, соединяющего u с v .
2. Relabel: операция Relabel применяется к переполненной вершине u для увеличения ее высоты. Алгоритм находит соседнюю вершину v вершины u , которая имеет минимальную высоту. Затем он обновляет

    *** QuickLaTeX не может скомпилировать формулу:
   
   
   *** Сообщение об ошибке:
   Ошибка: Нечего показывать, формула пуста
   

Алгоритм

Общий алгоритм push - relabel использует функцию инициализации перед потоком. Функция представлена ниже, а затем алгоритм.

Initialize-Preflow

1. initialize height and excess flow of every vertex to 0

2. set height of source to number of vertices

3. initialize flow of each edge to 0

4. for each adjacent vertex of source, set its flow and excess flow to capacity of edge connecting them

Generic-Push-Relabel

1. Initialize-Preflow

2. while there exists an applicable push or relabel operation

3. select an applicable push or relabel operation and perform it

4. return flow

FIFO Push-Relabel против Push-Relabel

FIFO push relabel — это оптимизация исходной push relabel. Вместо того, чтобы тратить линейное время на поиск переполненной вершины, мы организуем все переполняющие вершины в очередь. Это позволяет нам найти переполняющую вершину за постоянное время . Это снижает временную сложность до O(V ³ ) с O(V ² E).

Реализация алгоритма FIFO Push-Relabel

Пример постановки задачи: в приведенном ниже коде ориентированный граф был инкапсулирован в классе DirectedGraph, который был реализован первым. Он содержит вложенный класс Vertex, который инкапсулирует ребро графа. Рассмотрим график, приведенный ниже –

Ребро от 0 -> 1 будет инкапсулировано вершинным объектом V(1, 3), где 1 — пункт назначения, а 3 — вес. Он будет храниться по индексу 0 матрицы смежности. Вот матрица смежности приведенного выше графа.

0: [[1, 3], [3, 4]]
1: [[2, 1]]
2: [[3, 2]]
3: []

Временная сложность: O(V ³ )