Рубрики

Алгоритм Push Relabel | Комплект 1 (Введение и Иллюстрация)

Дан график, который представляет сеть потоков, где каждое ребро имеет емкость. Также, учитывая две вершины источника 's' и приемника 't' в графе, найдите максимально возможный поток от s до t со следующими ограничениями:

а) Поток на ребре не превышает заданную мощность ребра.

б) Входящий поток равен исходящему потоку для каждой вершины, кроме s и t.

Например, рассмотрим следующий график из книги CLRS.

Максимально возможный поток на графике выше 23.

Мы обсудили алгоритм Форда Фулкерсона, который использует путь увеличения для вычисления максимального потока.

Алгоритм Push-Relabel

Подход Push-Relabel является более эффективным, чем алгоритм Форда-Фулкерсона. В этом посте обсуждается «универсальный» алгоритм Голдберга с максимальным потоком, который выполняется за время O (V 2 E) . Эта временная сложность лучше, чем O (E 2 V), которая является временной сложностью алгоритма Эдмонда-Карпа (реализация Форда-Фулкерсона на основе BFS). В O (V 3 ) существует алгоритм, основанный на методе push-relbel, который даже лучше, чем рассмотренный здесь.

Сходства с Ford Fulkerson

  • Как и Ford-Fulkerson, Push-Relabel также работает с остаточным графиком (Остаточный график сети потоков представляет собой график, который указывает дополнительный возможный поток. Если в остаточном графике есть путь от источника к стоку, то можно добавить поток) ,

Отличия от Форда Фулкерсона

  • Push-релабельный алгоритм работает в более локализованном виде. Вместо того, чтобы исследовать всю остаточную сеть, чтобы найти путь расширения, алгоритмы push-relbel работают с одной вершиной за раз (Источник: Книга CLRS).
  • В Ford-Fulkerson чистая разница между общим оттоком и общим притоком для каждой вершины (за исключением источника и приемника) поддерживается на уровне 0. Алгоритм Push-Relabel позволяет притоку превышать отток до достижения конечного потока. В конечном потоке чистая разница равна 0 для всех, кроме источника и поглотителя.
  • Временная сложность более эффективна.

Интуиция позади алгоритма push-relbel (учитывая проблему потока жидкости) состоит в том, что мы рассматриваем ребра, поскольку водопроводные трубы и узлы являются соединениями. Считается, что источник находится на самом высоком уровне, и он посылает воду во все соседние узлы. Как только у узла есть избыток воды, он выталкивает воду к узлу меньшей высоты. Если вода попадает в локальную ловушку в вершине, вершина помечается, что означает, что ее высота увеличивается.

Ниже приведены некоторые полезные факты для рассмотрения, прежде чем мы перейдем к алгоритму.

  • С каждой вершиной связана переменная высоты и избыточный поток. Высота используется, чтобы определить, может ли вершина толкать поток к смежной или нет (вершина может толкать поток только к вершине меньшей высоты). Избыточный поток — это разность общего потока, поступающего в вершину, за вычетом общего потока, выходящего из вершины.
         Excess Flow of u = Total Inflow to u - 
                            Total Outflow from u
  • Как Форд Фулкерсон. с каждым ребром связан поток (который указывает текущий ток) и емкость

Ниже приведены абстрактные шаги полного алгоритма.

Push-Relabel Algorithm 
1) Initialize PreFlow : Initialize Flows 
   and Heights 

2) While it is possible to perform a Push() or 
   Relablel() on a vertex
   // Or while there is a vertex that has excess flow
           Do Push() or Relabel()

// At this point all vertices have Excess Flow as 0 (Except source
// and sink)
3) Return flow.

В алгоритме Push-Relabel есть три основных операции

  1. Initialize PreFlow () Инициализирует высоты и потоки всех вершин.
    Preflow() 
    1) Initialize height and flow of every vertex as 0.
    2) Initialize height of source vertex equal to total 
       number of vertices in graph.
    3) Initialize flow of every edge as 0.
    4) For all vertices adjacent to source s, flow and  
       excess flow is equal to capacity initially.
  2. Push () используется для создания потока из узла, который имеет избыточный поток. Если у вершины есть избыточный поток, и есть соседний с меньшей высотой (в остаточном графе), мы продвигаем поток из вершины в соседний с меньшей высотой. Количество проталкиваемого потока через трубу (кромку) равно минимуму избыточного потока и вместимости кромки.
  3. Операция Relabel () используется, когда вершина имеет избыточный поток, и ни одна из ее смежных не находится на более низкой высоте. Мы в основном увеличиваем высоту вершины, чтобы мы могли выполнить push (). Чтобы увеличить высоту, мы выбираем минимальную смежную высоту (в остаточном графе, т. Е. Соседнюю, к которой мы можем добавить поток) и добавляем к ней 1.

Обратите внимание, что вышеуказанные операции выполняются на остаточном графике (например, Ford-Fulkerson ).

Иллюстрация:

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

Всякий раз, когда мы нажимаем или добавляем поток из вершины u в v, мы делаем следующие обновления в остаточном графе:
1) Вычитаем поток из емкости ребра из u в v. Если емкость ребра становится равной 0, то ребро больше не существует в остаточном графе.
2) Добавляем поток в емкость ребра от v до u.

For example, consider two vertices u an v.

In original graph
        3/10
   u ---------> v
    3 is current flow from u to v and
    10 is capacity of edge from u to v.

In residual Graph, there are two edges corresponding
to one edge shown above.
         7
   u ---------> v

         3
   u <--------- v 
    1. Начальный заданный поток граф.
    2. ,

    3. После операции PreFlow. На остаточном графике имеется ребро от A до S с емкостью 3 и без ребра от S до A.
    4. ,

    5. Выделенная вершина перемаркирована (высота становится 1), так как она имеет избыточный поток и нет смежных с меньшей высотой. Новая высота равна минимуму высот смежного плюс 1. В остаточном графе есть два смежных с вершиной A, один — S, а другой — B. Высота S — 4, а высота B — 0. Минимум этих двух высота равна 0. Мы берем минимум и добавляем 1 к нему.
    6. ,

    7. Выделенная вершина имеет избыточный поток, и есть смежная с меньшей высотой, поэтому происходит push (). Избыточный поток вершины A равен 2, а пропускная способность ребра (A, B) равна 1. Следовательно, величина выталкиваемого потока равна 1 (минимум из двух значений).
    8. ,

    9. Выделенная вершина перемаркирована (высота становится 1), так как она имеет избыточный поток и нет смежных с меньшей высотой.
    10. ,

    11. Выделенная вершина имеет избыточный поток, и есть смежная с меньшей высотой, поэтому flow () перемещается из B в T.
    12. ,

    13. Выделенная вершина перемаркирована (высота становится 5), так как она имеет избыточный поток, и нет смежных с меньшей высотой.
    14. ,

    15. Выделенная вершина имеет избыточный поток, и есть смежная с меньшей высотой, поэтому происходит push ().
    16. ,

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

    Приведенный выше пример взят отсюда .

    Алгоритм Push Relabel | Набор 2 (реализация)

    Эта статья предоставлена Сиддхартом Лалвани . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

    Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

    Рекомендуемые посты:

    Алгоритм Push Relabel | Комплект 1 (Введение и Иллюстрация)

    0.00 (0%) 0 votes