Алгоритм Relabel-to-Front

Алгоритм relabel-to-front используется для определения максимального потока в сети. Алгоритм повторной метки на передний план более эффективен, чем общий метод push-relabel. В методе push-relabel мы можем применять основные операции push и relabel в любом порядке. Алгоритм relabel-to-front тщательно выбирает порядок и эффективно управляет сетевыми структурами данных.

Во-первых, нам нужно понять основные операции, то есть push и переназначение :
С каждой вершиной в сети связаны 2 переменные : переменная высоты (h) и избыточный расход (e) .

1. Push: если вершина имеет избыточный поток и есть соседний узел с меньшей высотой (в остаточном графе), то мы проталкиваем поток из вершины в узел с меньшей высотой.
2. Relabel: если вершина имеет избыточный поток и нет доступных соседних узлов с меньшей высотой, мы используем операцию relabel, чтобы увеличить высоту вершины, чтобы она могла выполнять операцию push.

Алгоритм переназначения на передний план поддерживает список вершин в сети. Он начинается с начала списка и несколько раз выбирает вершину u, выходящую за пределы вершины, и выполняет над ней операцию разгрузки.
Операция разгрузки - это выполнение операции push и повторной маркировки до тех пор, пока в вершине u не будет положительного избыточного потока (e)
Если вершина помечается заново, она перемещается в начало списка, и алгоритм снова выполняет сканирование.

Алгоритм:

• Инициализируйте предварительный поток и высоту теми же значениями, что и в общем алгоритме push-relabel.
• Инициализируйте список L, который содержит все вершины, кроме источника и приемника .
• Инициализировать текущий указатель каждой вершины u первой вершиной в списке соседей u N. Список соседей N содержит те вершины, для которых есть остаточное ребро.
• Пока алгоритм достигает конца списка L.
  • Выберите вершину u из списка L и выполните операцию разряда.
  • Если u был изменен в результате разряда, переместите u в начало списка.
  • Если u был перемещен в начало списка, вершина в следующей итерации будет следующей за u в ее новой позиции в списке.

Пример:
Рассмотрим данную потоковую сеть. Справа показан исходный список L = (B, C), где изначально u = B.

После операции инициализации предварительного потока. Под каждой вершиной в списке L находится список ее соседей N с текущим соседом в кружке.

Вершина B подвергается операции разгрузки, так как имеет избыточный поток 3 (e = 3). В вершине B нет узла с меньшей высотой, поэтому она выполняет операцию переназначения (h = 1) и подталкивает поток 1 к вершине C.

В вершине B все еще есть избыточный поток 2 (e = 2), поэтому она выполняет операцию переназначения (h = 5) и перемещает поток 2 в вершину A. Поскольку вершина B перемаркирована, она остается в начале списка. Теперь вершина C подвергается сбросу, так как имеет избыточный поток 1 (e = 1).

Вершина C выполняет операцию переназначения (h = 1) и подталкивает поток 1 к узлу D. Поскольку вершина C выполнила операцию переназначения, она перемещается в начало списка.

Вершина B теперь следует за вершиной C в L, но B не имеет избыточного потока. RELABEL-TO-FRONT достиг конца списка L и завершается. Вершины переполнения отсутствуют, поэтому предварительный поток является максимальным. Здесь максимальный расход равен 1.

Сложность времени: выполняется за O (V ³ ) времени в сети G = (V, E) . Таким образом, он более эффективен, чем общий алгоритм push-relabel , который выполняется за время O (V ² E) .

Ссылки: Введение в алгоритмы, 3-е издание Клиффорда Стейна, Томаса Х. Кормена, Чарльза Э. Лейзерсона, Рональда Л. Ривеста

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.