Рубрики

Алгоритм Форда-Фулкерсона для задачи о максимальном расходе

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

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

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

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

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

Необходимое условие: проблема с максимальным расходом Введение

Ford-Fulkerson Algorithm 
The following is simple idea of Ford-Fulkerson algorithm:
1) Start with initial flow as 0.
2) While there is a augmenting path from source to sink. 
           Add this path-flow to flow.
3) Return flow.

Сложность времени: временная сложность вышеупомянутого алгоритма O (max_flow * E). Мы запускаем цикл, пока существует расширяющийся путь. В худшем случае мы можем добавить 1 единичный поток в каждой итерации. Следовательно, сложность времени становится O (max_flow * E).

Как реализовать приведенный выше простой алгоритм?
Давайте сначала определим концепцию остаточного графа, которая необходима для понимания реализации.
Остаточный график потока сети представляет собой график, который указывает дополнительный возможный поток. Если в остаточном графе есть путь от источника к стоку, то можно добавить поток. Каждое ребро остаточного графа имеет значение, называемое остаточной емкостью, которое равно исходной емкости ребра за вычетом тока. Остаточная емкость — это в основном текущая емкость края.
Давайте теперь поговорим о деталях реализации. Остаточная емкость равна 0, если между двумя вершинами остаточного графа нет ребра. Мы можем инициализировать остаточный граф как исходный граф, так как нет начального потока, и первоначально остаточная емкость равна исходной емкости. Чтобы найти путь расширения, мы можем сделать BFS или DFS остаточного графа. Мы использовали BFS в приведенной ниже реализации. Используя BFS, мы можем выяснить, существует ли путь от источника к приемнику. BFS также создает родительский массив []. Используя массив parent [], мы проходим по найденному пути и находим возможный поток по этому пути, находя минимальную остаточную емкость вдоль пути. Позже мы добавим найденный поток пути к общему потоку.
Важно то, что нам нужно обновить остаточные мощности в остаточном графике. Мы вычитаем поток пути из всех ребер вдоль пути и добавляем поток пути вдоль обратных ребер. Нам нужно добавить поток пути вдоль обратных ребер, потому что позже может потребоваться отправить поток в обратном направлении (см., Например, следующую ссылку).

http://espressocode.top/max-flow-problem-introduction/

Ниже приведена реализация алгоритма Форда-Фулкерсона. Для простоты граф представлен в виде 2D-матрицы.

C ++

// C ++ программа для реализации алгоритма Форда Фулкерсона
#include <iostream>
#include <limits.h>
#include <string.h>
#include <queue>

using namespace std;

  
// Количество вершин в данном графе
#define V 6

  
/ * Возвращает true, если есть путь от источника 's' к стоку 't' в

  остаточный граф. Также заполняет parent [] для хранения пути * /

bool bfs(int rGraph[V][V], int s, int t, int parent[])

{

    // Создаем посещенный массив и отмечаем все вершины как не посещенные

    bool visited[V];

    memset(visited, 0, sizeof(visited));

  

    // Создать очередь, поставить в очередь исходную вершину и отметить исходную вершину

    // как посетил

    queue <int> q;

    q.push(s);

    visited[s] = true;

    parent[s] = -1;

  

    // Стандартный цикл BFS

    while (!q.empty())

    {

        int u = q.front();

        q.pop();

  

        for (int v=0; v<V; v++)

        {

            if (visited[v]==false && rGraph[u][v] > 0)

            {

                q.push(v);

                parent[v] = u;

                visited[v] = true;

            }

        }

    }

  

    // Если мы достигли стока в BFS, начиная с источника, то возвращаем

    // правда, иначе ложь

    return (visited[t] == true);

}

  
// Возвращает максимальный поток от s до t в данном графике

int fordFulkerson(int graph[V][V], int s, int t)

{

    int u, v;

  

    // Создание остаточного графа и заполнение остаточного графа

    // заданные мощности в исходном графике как остаточные мощности

    // в остаточном графе

    int rGraph[V][V]; // Остаточный граф, где rGraph [i] [j] указывает

                     // остаточная емкость ребра от i до j (если есть

                     // это ребро Если rGraph [i] [j] равен 0, то нет)

    for (u = 0; u < V; u++)

        for (v = 0; v < V; v++)

             rGraph[u][v] = graph[u][v];

  

    int parent[V];  // Этот массив заполняется BFS и для хранения пути

  

    int max_flow = 0;  // изначально нет потока

  

    // Увеличиваем поток, пока путь от источника к стоку

    while (bfs(rGraph, s, t, parent))

    {

        // Находим минимальную остаточную емкость ребер вдоль

        // путь заполнен BFS. Или мы можем сказать, найти максимальный поток

        // через найденный путь.

        int path_flow = INT_MAX;

        for (v=t; v!=s; v=parent[v])

        {

            u = parent[v];

            path_flow = min(path_flow, rGraph[u][v]);

        }

  

        // обновляем остаточные емкости ребер и обратных ребер

        // по пути

        for (v=t; v != s; v=parent[v])

        {

            u = parent[v];

            rGraph[u][v] -= path_flow;

            rGraph[v][u] += path_flow;

        }

  

        // Добавить поток пути к общему потоку

        max_flow += path_flow;

    }

  

    // Возвращаем общий поток

    return max_flow;

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    // Давайте создадим график, показанный в приведенном выше примере

    int graph[V][V] = { {0, 16, 13, 0, 0, 0},

                        {0, 0, 10, 12, 0, 0},

                        {0, 4, 0, 0, 14, 0},

                        {0, 0, 9, 0, 0, 20},

                        {0, 0, 0, 7, 0, 4},

                        {0, 0, 0, 0, 0, 0}

                      };

  

    cout << "The maximum possible flow is " << fordFulkerson(graph, 0, 5);

  

    return 0;

}

Джава

// Java-программа для реализации алгоритма Форда Фулкерсона

import java.util.*;

import java.lang.*;

import java.io.*;

import java.util.LinkedList;

  

class MaxFlow

{

    static final int V = 6;    // Количество вершин в графе

  

    / * Возвращает true, если есть путь от источника 's' до приемника

      't' в остаточном графе. Также заполняет parent [] для хранения

      путь */

    boolean bfs(int rGraph[][], int s, int t, int parent[])

    {

        // Создаем посещенный массив и помечаем все вершины как не

        // посетил

        boolean visited[] = new boolean[V];

        for(int i=0; i<V; ++i)

            visited[i]=false;

  

        // Создать очередь, поставить в очередь исходную вершину и пометить

        // исходная вершина как посещенная

        LinkedList<Integer> queue = new LinkedList<Integer>();

        queue.add(s);

        visited[s] = true;

        parent[s]=-1;

  

        // Стандартный цикл BFS

        while (queue.size()!=0)

        {

            int u = queue.poll();

  

            for (int v=0; v<V; v++)

            {

                if (visited[v]==false && rGraph[u][v] > 0)

                {

                    queue.add(v);

                    parent[v] = u;

                    visited[v] = true;

                }

            }

        }

  

        // Если мы достигли стока в BFS, начиная с источника, то

        // вернуть true, иначе false

        return (visited[t] == true);

    }

  

    // Возвращает максимальный поток от s до t в данном графике

    int fordFulkerson(int graph[][], int s, int t)

    {

        int u, v;

  

        // Создать остаточный график и заполнить остаточный график

        // с заданными возможностями в исходном графе как

        // остаточные мощности в остаточном графе

  

        // Остаточный граф, где rGraph [i] [j] указывает

        // остаточная емкость ребра от i до j (если есть

        // это ребро Если rGraph [i] [j] равен 0, то есть

        // нет)

        int rGraph[][] = new int[V][V];

  

        for (u = 0; u < V; u++)

            for (v = 0; v < V; v++)

                rGraph[u][v] = graph[u][v];

  

        // Этот массив заполняется BFS и для хранения пути

        int parent[] = new int[V];

  

        int max_flow = 0// изначально нет потока

  

        // Увеличиваем поток, пока есть путь от источника

        // тонуть

        while (bfs(rGraph, s, t, parent))

        {

            // Находим минимальную остаточную емкость стружки

            // по пути, заполненному BFS. Или мы можем сказать

            // найти максимальный поток по найденному пути.

            int path_flow = Integer.MAX_VALUE;

            for (v=t; v!=s; v=parent[v])

            {

                u = parent[v];

                path_flow = Math.min(path_flow, rGraph[u][v]);

            }

  

            // обновляем остаточные емкости ребер и

            // перевернуть ребра вдоль пути

            for (v=t; v != s; v=parent[v])

            {

                u = parent[v];

                rGraph[u][v] -= path_flow;

                rGraph[v][u] += path_flow;

            }

  

            // Добавить поток пути к общему потоку

            max_flow += path_flow;

        }

  

        // Возвращаем общий поток

        return max_flow;

    }

  

    // Программа драйвера для проверки вышеуказанных функций

    public static void main (String[] args) throws java.lang.Exception

    {

        // Давайте создадим график, показанный в приведенном выше примере

        int graph[][] =new int[][] { {0, 16, 13, 0, 0, 0},

                                     {0, 0, 10, 12, 0, 0},

                                     {0, 4, 0, 0, 14, 0},

                                     {0, 0, 9, 0, 0, 20},

                                     {0, 0, 0, 7, 0, 4},

                                     {0, 0, 0, 0, 0, 0}

                                   };

        MaxFlow m = new MaxFlow();

  

        System.out.println("The maximum possible flow is " +

                           m.fordFulkerson(graph, 0, 5));

  

    }

}

питон

# Python программа для реализации алгоритма Форда Фулкерсона

   

from collections import defaultdict

   
# Этот класс представляет ориентированный граф с использованием представления матрицы смежности

class Graph:

   

    def __init__(self,graph):

        self.graph = graph # остаточный график

        self. ROW = len(graph)

        # self.COL = len (gr [0])

          

   

    '' 'Возвращает true, если есть путь от источника' s 'к стоку' t 'в

    остаточный граф. Также заполняет parent [] для хранения пути '' '

    def BFS(self,s, t, parent):

  

        # Отметить все вершины как не посещенные

        visited =[False]*(self.ROW)

          

        # Создать очередь для BFS

        queue=[]

          

        # Отметить исходный узел как посещенный и поставить его в очередь

        queue.append(s)

        visited[s] = True

           

         # Стандартный цикл BFS

        while queue:

  

            # Освободить вершину из очереди и распечатать ее

            u = queue.pop(0)

          

            # Получить все смежные вершины в удаленной вершине u

            # Если соседний объект не посещался, отметьте его

            # посетил и поставил в очередь

            for ind, val in enumerate(self.graph[u]):

                if visited[ind] == False and val > 0 :

                    queue.append(ind)

                    visited[ind] = True

                    parent[ind] = u

  

        # Если мы достигли приемника в BFS, начиная с исходного кода, вернемся

        # верно, иначе неверно

        return True if visited[t] else False

              

      

    # Возвращает максимальный поток от s до t в данном графике

    def FordFulkerson(self, source, sink):

  

        # Этот массив заполняется BFS и для хранения пути

        parent = [-1]*(self.ROW)

  

        max_flow = 0 # Нет потока изначально

  

        # Увеличивать поток, пока есть путь от источника к раковине

        while self.BFS(source, sink, parent) :

  

            # Найти минимальную остаточную емкость ребер вдоль

            # путь заполнен BFS. Или мы можем сказать, найти максимальный поток

            # через найденный путь.

            path_flow = float("Inf")

            s = sink

            while(s !=  source):

                path_flow = min (path_flow, self.graph[parent[s]][s])

                s = parent[s]

  

            # Добавить поток пути к общему потоку

            max_flow +=  path_flow

  

            # обновить остаточные емкости ребер и обратных ребер

            # вдоль пути

            v = sink

            while(v !=  source):

                u = parent[v]

                self.graph[u][v] -= path_flow

                self.graph[v][u] += path_flow

                v = parent[v]

  

        return max_flow

  

   
# Создайте график, приведенный на диаграмме выше

  

graph = [[0, 16, 13, 0, 0, 0],

        [0, 0, 10, 12, 0, 0],

        [0, 4, 0, 0, 14, 0],

        [0, 0, 9, 0, 0, 20],

        [0, 0, 0, 7, 0, 4],

        [0, 0, 0, 0, 0, 0]]

  

g = Graph(graph)

  

source = 0; sink = 5

   

print ("The maximum possible flow is %d " % g.FordFulkerson(source, sink))

  
# Этот код предоставлен Ниламом Ядавом

C #

// C # программа для реализации
// алгоритма Форда Фулкерсона

using System;

using System.Collections.Generic;

  

public class MaxFlow

{

    static readonly int V = 6; // Количество вершин в графе

  

    / * Возвращает true, если есть путь

    от источника 's', чтобы поглотить 't' в остатке

    граф. Также заполняет parent [] для хранения

    путь */

    bool bfs(int [,]rGraph, int s, int t, int []parent)

    {

        // Создать посещенный массив и пометить

        // все вершины как не посещенные

        bool []visited = new bool[V];

        for(int i = 0; i < V; ++i)

            visited[i] = false;

  

        // Создать очередь, поставить в очередь исходную вершину и пометить

        // исходная вершина как посещенная

        List<int> queue = new List<int>();

        queue.Add(s);

        visited[s] = true;

        parent[s] = -1;

  

        // Стандартный цикл BFS

        while (queue.Count != 0)

        {

            int u = queue[0];

                queue.RemoveAt(0);

  

            for (int v = 0; v < V; v++)

            {

                if (visited[v] == false && rGraph[u, v] > 0)

                {

                    queue.Add(v);

                    parent[v] = u;

                    visited[v] = true;

                }

            }

        }

  

        // Если мы достигли раковины в BFS

        // начиная с источника, затем

        // вернуть true, иначе false

        return (visited[t] == true);

    }

  

    // Возвращает максимальный поток

    // от s до t в данном графе

    int fordFulkerson(int [,]graph, int s, int t)

    {

        int u, v;

  

        // Создать остаточный график и заполнить

        // остаточный граф с заданным

        // емкости в исходном графике как

        // остаточные мощности в остаточном графе

  

        // Остаточный граф, где rGraph [i, j]

        // указывает остаточную емкость

        // край от i до j (если есть

        // край. Если rGraph [i, j] равен 0, то

        // нет)

        int [,]rGraph = new int[V, V];

  

        for (u = 0; u < V; u++)

            for (v = 0; v < V; v++)

                rGraph[u, v] = graph[u, v];

  

        // Этот массив заполняется BFS и для хранения пути

        int []parent = new int[V];

  

        int max_flow = 0; // изначально нет потока

  

        // Увеличиваем поток, пока есть путь от источника

        // тонуть

        while (bfs(rGraph, s, t, parent))

        {

            // Находим минимальную остаточную емкость стружки

            // по пути, заполненному BFS. Или мы можем сказать

            // найти максимальный поток по найденному пути.

            int path_flow = int.MaxValue;

            for (v = t; v != s; v = parent[v])

            {

                u = parent[v];

                path_flow = Math.Min(path_flow, rGraph[u,v]);

            }

  

            // обновляем остаточные емкости ребер и

            // перевернуть ребра вдоль пути

            for (v = t; v != s; v = parent[v])

            {

                u = parent[v];

                rGraph[u,v] -= path_flow;

                rGraph[v,u] += path_flow;

            }

  

            // Добавить поток пути к общему потоку

            max_flow += path_flow;

        }

  

        // Возвращаем общий поток

        return max_flow;

    }

  

    // Код драйвера

    public static void Main ()

    {

        // Давайте создадим график, показанный в приведенном выше примере

        int [,]graph =new int[,] { {0, 16, 13, 0, 0, 0},

                                    {0, 0, 10, 12, 0, 0},

                                    {0, 4, 0, 0, 14, 0},

                                    {0, 0, 9, 0, 0, 20},

                                    {0, 0, 0, 7, 0, 4},

                                    {0, 0, 0, 0, 0, 0}

                                };

        MaxFlow m = new MaxFlow();

  

        Console.WriteLine("The maximum possible flow is " +

                        m.fordFulkerson(graph, 0, 5));

  

    }

}

  
/ * Этот код предоставлен PrinciRaj1992 * /


Выход:

The maximum possible flow is 23

Вышеприведенная реализация алгоритма Форда Фулкерсона называется алгоритмом Эдмондса-Карпа . Идея Эдмондса-Карпа заключается в использовании BFS в реализации Ford Fulkerson, поскольку BFS всегда выбирает путь с минимальным количеством ребер. Когда используется BFS, временная сложность в наихудшем случае может быть уменьшена до O (VE 2 ). Вышеупомянутая реализация использует представление матрицы смежности, хотя, когда BFS занимает время O (V 2 ), временная сложность вышеупомянутой реализации составляет O (EV 3 ) (См. Книгу CLRS для доказательства сложности времени)

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

Алгоритм Динка для Max-Flow.

Упражнение:
Измените вышеприведенную реализацию так, чтобы она выполнялась за время O (VE 2 ).

Ссылки:
http://www.stanford.edu/class/cs97si/08-network-flow-problems.pdf
Введение в алгоритмы 3-е издание Клиффорд Стейн, Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест

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

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

Алгоритм Форда-Фулкерсона для задачи о максимальном расходе

0.00 (0%) 0 votes