Maximum Flow | UnderSkyAi

Это 20-й день моего участия в августовском испытании обновлений. Ознакомьтесь с подробностями мероприятия: Испытание августовского обновления

Основные свойства Flow Networks

В теории графов сетевой поток определяется как ориентированный граф, содержащий начальную точку.Sисточник и пункт назначенияTarget и несколько ребер, соединяющих вершины. Каждое ребро имеет свою пропускную способностьCПропускная способность, которая является максимальным трафиком, который может разрешить ребро.

трафик в сетевом потоке $f$ Следующие условия должны быть выполнены

От узла $x$ поток к узлу $y$ трафик, не могу сравнить $edge(x,y)$ изcapacityеще большой, $f (х, у) ≤ с (х, у)$
Если определен подчиненный узел $x$ поток к узлу $y$ Поток имеет 5 единиц, $f(x,y)=5$ , то подчиненный узел $y$ поток к узлу $x$ Поток имеет -5 единиц, $f(y,x)=-5$
Для узлов, отличных от источника и цели на графике, сумма всего входящего трафика должна быть равна сумме всего исходящего трафика.
- То есть поток не будет увеличиваться или уменьшаться без причины, что можно расценивать как своего рода сохранение энергии.
- Возьмем в качестве примера следующий рисунок: поток в узел A равен 6, поток из узла A также равен 6, и то же верно для C и D.

Максимальный поток:Сеть позволяет из источникаSпоток течет до концаTМаксимальный трафик ARGET

Алгоритм Форда-Фалкерсона (или алгоритм Эдмондса-Карпа, если используется BFS) представлен ниже для решения этой проблемы.

Ford-Fulkerson Algorithm

Алгоритм Форда-Фалкерсона требует двух вспомогательных средств.

Остаточные сети
Увеличение путей

Residual Networks

Остаточная сеть представляет собой график оставшегося допустимого трафика для каждого ребра в графе. Следующий график является примером

Если все ребра на пути: S-A-C-D-T имеют поток 6 единиц, то эти ребра, $edge(S,A)$ , $edge(A,C)$ , $edge(C,D)$ , $edge(D,T)$ остатокемкостьОба должны быть минус 6. Например, $edge(S,A)$ Может удерживать только 3 единицы потока, $edge(C,D)$ Может удерживать только 1 единицу потока

как $edge(x,y)$ Там $f(x,y)$ единица расхода, тогда $edge(x,y)$ Вверхresidual capacityопределяется как:

$c_f(x,y)=c(x,y)-f(x,y)$
- $c(x,y)$ для исходного края (x, y)емкость
- $f(x,y)$ Указывает, сколько трафика у края (x, y) в настоящее время
- $c_f(x,y)$ Указывает, сколько трафика может быть размещено на краю (x, y)

Residual Networksтакже является ориентированным графом, где:

Набор вершин точно такой же, как исходный ориентированный граф.
Емкость ребраresidual capacityзаменить, как показано ниже

Самое главное, если $edge(A,C)$ 6 единиц трафика через $f(A,C)=6$ , то в егоResidual Networks, ребро из вершины C в вершину A будет сгенерировано соответственно $edge(C,A)$ , и имеет 6 единицresidual capacity $c_f(C,A)=6$

Какой смысл это делать? Можно использоватьЕсли вы хотите изменить направление движенияпонять

Например, предположив, что начальное состояние теперь восстановлено (нет потоков трафика), теперь через Путь проходят 2 единицы трафика: S-C-A-B-T, но, поскольку нет пути из вершины C в вершину A $edge(C,A)$ ,следовательно $c(C,A)=0$ . Предполагая, что из вершины A в вершину C поступает 6 единиц потока (как показано на диаграмме выше), теперь можно начать с $edge(A,C)$ Включите 2 единицы потоказабрать, который назначен на $edge(A,B)$ на, пока $edge(A,C)$ , осталось только 4 единицы расхода, а окончательный результат показан слева на следующем рисунке.Residual Networksкак показано справа

Изображение ниже - еще один пример, найденный в Интернете.

Augmenting Paths

существуетResidual Networks, все доступно из исходниковSнаш подходит к концуTПуть цели, то есть все пути, которые могут увеличить трафик, называется Augmenting Paths (аугментирующие пути)

Возьмите приведенный выше рисунок в качестве примера, есть много возможностей для увеличения путей, таких как

Путь: S-A-B-T, 1~3 единицы потока
- Потому что на этом пути наименьшая пропускная способность среди всех ребер равна $c(S,A)=c(A,B)=3$ , поэтому допустимый размер потока составляет 1~3
Путь: S-C-B-D-T, 1~2 единицы потока
- Потому что на этом пути наименьшая пропускная способность среди всех ребер равна $c(B,D)=c(D,T)=2$ , поэтому допустимый размер потока составляет 1~2

Подводить итоги

видетьОбщий трафик, поступающий в настоящее время в Target, которые должны быть отмечены в левой части рисунка ниже, на краюflow/capacityнайти на карте
- Левая конечная точка притока на рисунке нижеTПоток Аргета составляет 8 единиц.
найтисколько еще трафика, то есть найтиAugmenting Paths, должен быть вResidual NetworksПосмотрите, как показано справа внизу
- Если она впадает в Путь: S-A-B-T, Путь: S-A-C-D-T, Путь: S-C-B-TНе превышайте минимальную остаточную емкость на путипоток, являются увеличивающими путями

Поговорив о двух вышеупомянутых концепциях, давайте объясним алгоритм алгоритма Форда-Фалкерсона.

существуетResidual NetworksПоиск поAugmenting Paths
- отBFS()Выполните поиск, чтобы убедиться, что увеличивающие пути, найденные каждый раз, должны проходить через наименьшее ребро.
- Найти усиливающие пути наМинимальная остаточная емкость, добавьте его вобщий поток
- снова сМинимальная остаточная емкостьвозобновитьResidual Networksна краюresidual capacity
Повторяйте вышеуказанные шаги до тех пор, пока не останетсяAugmenting Pathsдо того как

Возьмите приведенное выше изображение в качестве примера. Шаги для определения максимального расхода следующие:

начать сflow = 0Инициализировать остаточные сети

На рисунке сbfs()найти изSприбытьTПуть с наименьшим ребром: S-A-B-T
- bfs()Может быть найдено три кратчайших пути, вот пример S-A-B-T

Наблюдайте за краем пути: S-A-B-T и найдите $edge(A,B)$ имеет самый маленькийresidual capacity $c_f(A,B)=3$ , поэтому обновите:Общий поток увеличился на 3
Обновить остаточную емкость ребра
- $c_f(S,A)=c(S,A)-f(S,A)=9-3=6$
- $c_f(A,S)=c(A,S)-f(A,S)=0+3=3$
- $c_f(A,B)=c(A,B)-f(A,B)=3-3=0$
- $c_f(B,A)=c(B,A)-f(B,A)=0+3=3$
- $c_f(B,T)=c(B,T)-f(B,T)=9-3=6$
- $c_f(T,B)=c(T,B)-f(T,B)=0+3=3$

в пути, сbfs()найти изS*прибытьTПуть с наименьшим ребром: S-C-D-T

Наблюдайте за краем пути: S-C-D-T и найдите $edge(C,D)$ имеет самый маленькийresidual capacity $c_f(C,D)=7$ , поэтому обновите:Общий поток увеличился на 7
Обновить остаточную емкость ребра
- $c_f(S,C)=c(S,C)-f(S,C)=9-7=2$
- $c_f(C,S)=c(C,S)-f(C,S)=0+7=7$
- $c_f(C,D)=c(C,D)-f(C,D)=7-7=0$
- $c_f(D,C)=c(D,C)-f(D,C)=0+7=7$
- $c_f(D,T)=c(D,T)-f(D,T)=8-7=1$
- $c_f(T,D)=c(D,T)-f(T,D)=0+7=7$

Затем повторите вышеуказанные шаги:Обновите остаточные сети, найдите увеличивающиеся пути

Найти путь: S-C-B-T

возобновитьResidual Networks

Найти путь: S-A-C-B-T

возобновитьResidual Networks

Найти путь: S-A-C-B-D-T

возобновитьResidual Networks

Найдите максимальный поток = 17

Полный код выглядит следующим образом

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Graph {
private:
    int num_vertex; //顶点
    vector<vector<int>> map; // 邻接矩阵
public:
    Graph():num_vertex(0){};
    Graph(int n);
    void AddEdge(int from, int to, int capacity);
    void FordFulkerson(int s, int t);
    bool BfsFindExistingPath(vector<vector<int>> graph, int* predecessor, int s, int t);
    int MinCapacity(vector<vector<int>> graph, int* predecessor, int t);
};

Graph::Graph(int n):num_vertex(n) {
    map.resize(num_vertex);
    for (int i = 0; i < num_vertex; i++)
        map[i].resize(num_vertex);
}

bool Graph::BfsFindExistingPath(vector<vector<int>> graph, int* predecessor, int s, int t) {
    int visited[num_vertex];
    for (int i = 0; i < num_vertex; i++) {
        visited[i] = 0; // 0 表示没有访问过
        predecessor[i] = -1;
    }

    queue<int> queue;
    queue.push(s);
    visited[s] = 1; // 1 表示访问过
    while (!queue.empty()) {
        int vertex = queue.front(); queue.pop();
        for (int j = 0; j < num_vertex; j++) {
            if (graph[vertex][j] != 0 && visited[j] == 0) {
                queue.push(j);
                visited[j] = 1;
                predecessor[j] = vertex;
            }
        }
    }
    return (visited[t] == 1); // 若t被访问过，表示有path从s到t
}

int Graph::MinCapacity(vector<vector<int>> graph, int* predecessor, int t) {
    int min = 0x3f3f3f; // 确保min会更新，假设graph上的capacity都小于0x3f3f3f
    
    // 用predecessor[idx]和idx表示一条edge
    // 找到 从s到t 的path中，capacity最小的值，存入min
    for (int idx = t; predecessor[idx] != -1; idx = predecessor[idx])
        if (graph[predecessor[idx]][idx] != 0 && graph[predecessor[idx]][idx] < min)
            min = graph[predecessor[idx]][idx];
    return min;
}

void Graph::FordFulkerson(int s, int t) {
    vector<vector<int>> graphResidual(map);
    int maxflow = 0;
    int predecessor[num_vertex];

    // bfs find augmeting path
    while (BfsFindExistingPath(graphResidual, predecessor, s, t)) {
        int min_capacity = MinCapacity(graphResidual, predecessor, t);
        maxflow = maxflow + min_capacity;
        for (int y = t; y != s; y= predecessor[y]) {
            // update residual graph
            int x = predecessor[y];
            graphResidual[x][y] -= min_capacity;
            graphResidual[y][x] += min_capacity;
        }
    }
    cout << "Maximum Flow: " << maxflow << endl;
}

void Graph::AddEdge(int from, int to, int capacity) {
    map[from][to] = capacity;
}

int main() {
    Graph g(6);
    g.AddEdge(0, 1, 9);g.AddEdge(0, 3, 9);
    g.AddEdge(1, 2, 3);g.AddEdge(1, 3, 8);
    g.AddEdge(2, 4, 2);g.AddEdge(2, 5, 9);
    g.AddEdge(3, 2, 7);g.AddEdge(3, 4, 7);
    g.AddEdge(4, 2, 4);g.AddEdge(4, 5, 8);

    g.FordFulkerson(0, 5); // 指定source为0，target为5
    return 0;
}