본문 바로가기
Data Structure & Algorithm/알고리즘

포드 풀커슨 / 에드몬드 카프 알고리즘

by 별준 2022. 4. 20.

Contents

  • 포드 풀커슨(Ford-Fulkerson) 알고리즘
  • 에드몬드 카프(Edmonds-Karp) 알고리즘

선형 계획법과 치환 (2) - Network Flow, Bipartite Matching

위의 포스팅에서 네트워크 유량(network flow)에 관련한 내용들에 대해 다루었습니다. 여기서는 선형계획법과 심플렉스 방법에 대해 초점을 맞추어서 이야기를 했었는데, 이번 포스팅에서는 네트워크 유량 문제를 해결하는 알고리즘들에 대해 초점을 맞추어서 이야기해보고자 합니다. 알아볼 알고리즘은 포드 풀커슨 알고리즘과 애드몬드 카프 알고리즘입니다.

 

우선 위의 포스팅에서 사용했던 네트워크 유량을 나타내는 그래프를 가져오겠습니다.

그래프 (a)가 바로 네트워크를 나타내는 그래프입니다. 이 그래프의 간선에는 길이와 같은 가중치가 아닌 용량(capacity)가 부과되어 있습니다. 그리고 두 정점을 잇는 간선 (u, v)가 있을 때, 정점 u에서 정점 v로 간선의 최대 용량 이하만큼 유량(flow)를 흘려보낼 수 있습니다.

(간선은 방향이 있을 수도 있고, 없을 수도 있습니다)

 

위 그래프 (a)에서 우리가 풀고자 하는 문제는 source 정점인 s에서 sink 정점 t까지 흘려보낼 수 있는 최대 유량을 계산하는 것입니다.

 

먼저 네트워크(G = (V, E)인, 유향 그래프)가 만족해야 하는 특성을 살펴보겠습니다.

  • 간선에 흐르는 유량은 그 간선의 용량을 초과해서는 안됩니다. 각 간선 e에 흐르는 유량이 \(f_e\)이고, 그 간선의 용량이 \(c_e\)일 때, 모든 e에 대해서 다음의 조건을 만족해야 합니다: \(0 \leq f_e \leq c_e\)
  • s와 t를 제외한 모든 정점 u에서, u로 들어오는 총 유량과 u에서 나가는 총 유량은 동일해야 합니다. 즉, 유량은 보존됩니다.

\[\sum_{(w, u) \in E} f_{wu} = \sum_{(u, z) \in E} f_{uz}\]

  • 간선 (u, v)의 역간선 (v, u)이 존재할 수 있는데, 이는 역방향으로 음의 유량이 흐르고 있는 것으로 취급합니다. 다른 의미로는 (u, v)로 이미 흐른 유량을 역방향으로 흐르는 양만큼 취소한다고 생각할 수 있습니다.

 

이러한 특성들을 만족시키면서 s에서 t로 흘려보낼 수 있는 최대 유량(maximum flow)을 구하는 것인데, 위 예제에서는 7이 됩니다.

 

최대 유량을 구하는 알고리즘은 꽤 많은데, 이번 포스팅에서는 포드 풀커슨 알고리즘와 에드몬드 카프 알고리즘에 대해 살펴보겠습니다. 사실 두 알고리즘은 거의 동일하다고 볼 수 있습니다. 단, 시간복잡도에서 차이가 있습니다.

 

포드-풀커슨 알고리즘

포드 풀커슨 알고리즘의 동작은 다음과 같습니다.

 

출처 : wikipedia(Ford-Fulkerson algorithm)

  1. 먼저 주어진 그래프의 모든 간선 (u, v)에 대해 현재 u에서 v로 흐르는 유량 f(u, v)를 0으로 초기화합니다.
  2. 모든 간선 (u, v)에 대해 \(c_f (u, v) > 0\)인 \(G_f\)에서 s에서 t로 가는 경로 p가 있는 경우 아래를 반복한다.
    1. \(c_f(p) = \text{min}\{c_f(u,v) : (u, v) \in p\}\)를 찾는다.
    2. 각 간선 (u, v) \(\in\) p에 대해 아래를 반복
      1. \(f(u, v) \leftarrow f(u, v) + c_f(p)\) (경로를 따라 유량을 흘려보냄)
      2. \(f(v, u) \leftarrow f(v, u) - c_f(p)\) (역방향으로 유량을 흘려보냄)

위 알고리즘의 2번째 스텝에서 경로를 찾는 방법은 DFS나 BFS를 사용하는 것입니다. 여기서 DFS를 사용하는 것이 포드 풀커슨 알고리즘이고, BFS를 사용하는 것이 에드몬드 카프 알고리즘이 됩니다.

 

DFS의 시간복잡도가 매 반복 당 O(\(|V| + |E|\)) 입니다. 그리고 그래프에서의 최대 유량이 f라고 한다면, s에서 t로 가는 경로를 찾았을 때 최소 1씩은 유량을 흘려보낼 수 있습니다. 따라서 경로를 찾는 루프는 최대 f번 실행될 수 있습니다. 따라서 포드 풀커슨 알고리즘의 시간복잡도는 O(\((|V|+|E|)f\))인데, 보통 E가 V보다 훨씬 더 크기 때문에 O(\(|E|f\))가 됩니다.

 

link에서 잘 보여주고 있는데, 오직 1씩 흘려보내는 최악의 경우 때문에 문제가 발생할 수 있습니다.

초기에 위와 같은 그래프가 있다고 가정해보겠습니다. 여기서는 A에서 D로 흘려보낼 수 있는 최대 유량을 구해야 합니다. A->B->D와 A->C->D의 경로를 찾으면 흘려보낼 수 있는 유량이 최대 2000이라는 것을 바로 알 수 있지만,

DFS에 의해서 A->B->C->D 경로를 찾고, 유량을 1만 흘려보내게 될 수 있습니다. 그리고 다음에는

위와 같이 A->C->B->D 경로를 찾아서 또 유량을 1만 흘려보내게 됩니다. 이렇게만 경로를 찾게 되면, 결국 위의 경로를 1998번 더 찾고, 결국은 알고리즘을 종료하게 됩니다.

총 경로 2개만 찾으면 해결할 수 있던 문제가 2000번의 경로를 찾아야 해결될 수 있습니다.

 

이 문제는 경로를 찾는 방법을 DFS가 아닌 BFS로 찾아, s에서 t로 가는 가장 짧은 경로를 바로바로 찾아내면 해결할 수 있습니다. 이 알고리즘이 바로 에드몬드 카프 알고리즘입니다. BFS 방법을 사용하면 시간복잡도는 O(\(|V||E|^2\))로 줄어들게 됩니다.

 

에드몬드 카프 알고리즘 (C++ 구현)

이미 이 알고리즘에 대해서는 위에서 다 설명한 것 같습니다. 기본적인 방법은 위에서 설명한 포드 풀커슨 알고리즘과 같지만, s에서 t까지의 경로를 찾을 때 BFS 방법을 사용하면 됩니다.

알고리즘에 대해서는 위에서 충분히 살펴봤으니 구현으로 바로 넘어가도록 하겠습니다.

위의 문제에 대한 풀이 코드는 다음과 같습니다. s를 0번 정점, t를 6번 정점으로 두고, a에서 e까지의 정점은 1에서 5번 정점으로 설정하였습니다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

const int INF = 123456789;

void set_graph(std::vector<std::vector<int>>& graph, const int u, const int v, const int c)
{
    graph[u][v] = c;
    graph[v][u] = -c;
}

bool bfs(const int s, const int t, const int n, const std::vector<std::vector<int>>& graph, std::vector<int>& prev, std::vector<bool>& visited)
{
    // init value
    for (int i = 0; i < n; i++)
        visited[i] = false;

    // create a queue for BFS
    std::queue<int> q;

    // mark s node as visited and enqueue it
    q.push(s);
    visited[s] = true;

    int u{};
    while (!q.empty()) {
        u = q.front();
        q.pop();

        // get adjacent vertices
        for (int v = 0; v < n; v++) {
            if (visited[v] == false && graph[u][v] > 0) {
                q.push(v);
                visited[v] = true;
                prev[v] = u;
            }
        }
    }

    return visited[t];
}

int edmonds_karp(const int source, const int sink, const int n, std::vector<std::vector<int>>& graph)
{
    std::vector<bool> visited;
    std::vector<int> prev;

    // init value
    visited.resize(n, false);
    prev.resize(n, -1);

    int max_flow{ 0 };

    int path_flow{}, s{}, u{}, v{};
    while (bfs(source, sink, n, graph, prev, visited)) {
        path_flow = INF;

        // find minimum capacity of the edges along the path by BFS
        s = sink;
        while (s != source) {
            path_flow = std::min(path_flow, graph[prev[s]][s]);
            s = prev[s];
        }

        // add path flow to overall flow
        max_flow += path_flow;

        // update residual copacities of the edges and reverse edges along the path
        v = sink;
        while (v != source) {
            u = prev[v];
            graph[u][v] -= path_flow;
            graph[v][u] += path_flow;
            v = prev[v];
        }
    }

    return max_flow;
}

int main(int argc, char* argv[])
{
    std::vector<std::vector<int>> graph;
    // set graph
    int n = 7; // source:0, sink:6
    graph.resize(n, std::vector<int>(n, 0));
    set_graph(graph, 0, 1, 2); // s-a
    set_graph(graph, 0, 2, 1); // s-b
    set_graph(graph, 0, 3, 4); // s-c
    set_graph(graph, 1, 4, 2); // a-d
    set_graph(graph, 2, 4, 1); // b-d
    set_graph(graph, 3, 5, 5); // c-e
    set_graph(graph, 4, 3, 1); // d-c
    set_graph(graph, 4, 5, 0); // d-e
    set_graph(graph, 4, 6, 2); // d-t
    set_graph(graph, 5, 6, 5); // e-t

    // start
    auto result = edmonds_karp(0, n - 1, n, graph);
    std::cout << "Maximum flow: " << result << "\n";
}

코드에서 2중 벡터인 graph는 각 정점 사이의 용량의 값을 가지고 있습니다.

edmond_karp 함수에서 알고리즘이 수행되며, while 문의 조건은 bfs 함수를 호출하여 sink까지 도달이 가능하다면 계속해서 알고리즘을 반복하고, 도달하지 못했으면 바로 알고리즘을 중단하고 그때까지 계산한 s에서 t까지의 최대 유량을 반환하게 됩니다.

 

백준 6086 : 최대 유량

에드몬드 카프 알고리즘을 사용할 수 있는 적절한 문제가 백준에 있습니다.

https://www.acmicpc.net/problem/6086

 

6086번: 최대 유량

첫째 줄에 정수 N (1 ≤ N ≤ 700)이 주어진다. 둘째 줄부터 N+1번째 줄까지 파이프의 정보가 주어진다. 첫 번째, 두 번째 위치에 파이프의 이름(알파벳 대문자 또는 소문자)이 주어지고, 세 번째 위

www.acmicpc.net

이 문제는 최대 유량을 구하는 문제라는 것은 동일하지만, 무향 그래프로 주어집니다. 따라서, 방금 위에서 구현한 C++ 코드를 약간만 변형하면 이 문제는 해결할 수 있습니다.

여기서는 set_graph 함수가 변경되었으며, 변경 내용은 아래와 같습니다.

  • 각 간선이 중복해서 나올 수 있으므로, 간선의 용량을 초기화할 때 입력받은 값을 해당 간선의 용량을 저장하는 변수에 더해준다.
  • 양방향 그래프이므로 역간선의 용량도 음수가 아닌 양수로 설정한다.

그리고, 정점이 'a' ~ 'z', 'A' ~ 'Z' 까지 주어지므로 주어진 입력에 맞게 초기화를 수행하도록 수정해주고, 'A'에서 'Z'까지의 최대 유량을 구하도록 해줍니다(get_index 함수 참조).

구현 코드는 다음과 같습니다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

const int INF = 123456789;

void set_graph(std::vector<std::vector<int>>& graph, const int u, const int v, const int c)
{
    graph[u][v] += c;
    graph[v][u] += c;
}

bool bfs(const int s, const int t, const int n, const std::vector<std::vector<int>>& graph, std::vector<int>& prev, std::vector<bool>& visited)
{
    // init value
    for (int i = 0; i < n; i++)
        visited[i] = false;

    // create a queue for BFS
    std::queue<int> q;

    // mark s node as visited and enqueue it
    q.push(s);
    visited[s] = true;

    int u{};
    while (!q.empty()) {
        u = q.front();
        q.pop();

        // get adjacent vertices
        for (int v = 0; v < n; v++) {
            if (visited[v] == false && graph[u][v] > 0) {
                q.push(v);
                visited[v] = true;
                prev[v] = u;
            }
        }
    }

    return visited[t];
}

int edmonds_karp(const int source, const int sink, const int n, std::vector<std::vector<int>>& graph)
{
    std::vector<bool> visited;
    std::vector<int> prev;

    // init value
    visited.resize(n, false);
    prev.resize(n, -1);

    int max_flow{ 0 };

    int path_flow{}, s{}, u{}, v{};
    while (bfs(source, sink, n, graph, prev, visited)) {
        path_flow = INF;

        // find minimum capacity of the edges along the path by BFS
        s = sink;
        while (s != source) {
            path_flow = std::min(path_flow, graph[prev[s]][s]);
            s = prev[s];
        }

        // add path flow to overall flow
        max_flow += path_flow;

        // update residual copacities of the edges and reverse edges along the path
        v = sink;
        while (v != source) {
            u = prev[v];
            graph[u][v] -= path_flow;
            graph[v][u] += path_flow;
            v = prev[v];
        }
    }

    return max_flow;
}

char get_index(char u)
{
    if (u >= 'A' && u <= 'Z')
        return u - 'A';
    return u - 'a' + 26;
}

int main(int argc, char* argv[])
{
    std::vector<std::vector<int>> graph;
    // set graph
    int n = 52; // source:0(A), sink:25(Z)
    graph.resize(n, std::vector<int>(n, 0));

    int e, c;
    char u, v;
    scanf("%d", &e);
    for (int i = 0; i < e; i++) {
        scanf(" %c %c %d", &u, &v, &c);
        u = get_index(u);
        v = get_index(v);
        set_graph(graph, u, v, c);
    }

    // start
    auto result = edmonds_karp(get_index('A'), get_index('Z'), n, graph);
    std::cout << result << "\n";
}

 

 

백준 17412 : 도시 왕복하기 1

https://www.acmicpc.net/problem/17412

 

17412번: 도시 왕복하기 1

첫째 줄에 두 정수 N(3 ≤ N ≤ 400), P(1 ≤ P ≤ 10,000)이 주어진다. 다음 P개의 줄에는 각 길이 연결하는 출발 도시와 도착 도시의 번호가 주어지며, 두 번호는 다르다.

www.acmicpc.net

유사한 코드로 풀리는 문제가 하나 더 있습니다. 

 

N개의 도시가 P개의 단방향 길로 연결되어 있는데, 1번 도시에서 2번 도시까지 도착할 수 있는 경로를 구합니다. 이때, 한 경로에 포함된 길이 다른 경로에 포함되면 안되는데, 즉, 1번 도시에서 2번 도시까지 도달한 경로에서 사용한 간선(길)은 다시 사용하면 안됩니다. 따라서, 각 도시 사이의 간선의 용량을 1로 설정하고 문제를 풀면 됩니다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

const int INF = 123456789;

void set_graph(std::vector<std::vector<int>>& graph, const int u, const int v, const int c)
{
    graph[u][v] = c;
    //graph[v][u] = -c;
}

bool bfs(const int s, const int t, const int n, const std::vector<std::vector<int>>& graph, std::vector<int>& prev, std::vector<bool>& visited)
{
    // init value
    for (int i = 0; i < n; i++)
        visited[i] = false;

    // create a queue for BFS
    std::queue<int> q;

    // mark s node as visited and enqueue it
    q.push(s);
    visited[s] = true;

    int u{};
    while (!q.empty()) {
        u = q.front();
        q.pop();

        // get adjacent vertices
        for (int v = 0; v < n; v++) {
            if (visited[v] == false && graph[u][v] > 0) {
                q.push(v);
                visited[v] = true;
                prev[v] = u;
            }
        }
    }

    return visited[t];
}

int edmonds_karp(const int source, const int sink, const int n, std::vector<std::vector<int>>& graph)
{
    std::vector<bool> visited;
    std::vector<int> prev;

    // init value
    visited.resize(n, false);
    prev.resize(n, -1);

    int max_flow{ 0 };

    int path_flow{}, s{}, u{}, v{};
    while (bfs(source, sink, n, graph, prev, visited)) {
        path_flow = INF;

        // find minimum capacity of the edges along the path by BFS
        s = sink;
        while (s != source) {
            path_flow = std::min(path_flow, graph[prev[s]][s]);
            s = prev[s];
        }

        // add path flow to overall flow
        max_flow += path_flow;

        // update residual copacities of the edges and reverse edges along the path
        v = sink;
        while (v != source) {
            u = prev[v];
            graph[u][v] -= path_flow;
            graph[v][u] += path_flow;
            v = prev[v];
        }
    }

    return max_flow;
}

int main(int argc, char* argv[])
{
    std::vector<std::vector<int>> graph;
    // set graph
    int n{}, p{};
    scanf("%d %d", &n, &p);
    graph.resize(n, std::vector<int>(n, 0));

    int u, v;
    for (int i = 0; i < p; i++) {
        scanf("%d %d", &u, &v);
        u -= 1;
        v -= 1;
        set_graph(graph, u, v, 1);
    }

    // start
    auto result = edmonds_karp(0, 1, n, graph);
    std::cout << result << "\n";
}

처음에 역방향에 음수의 크기(-1)을 주어도 무관할 줄 알았는데, 유량과는 달리 역으로 흐르는 걸 포함시키면 안됩니다.

 

백준 2316 : 도시 왕복하기 2

이왕 문제를 푸는 김에 2316번 : 도시 왕복하기 2도 시도해봤습니다.

https://www.acmicpc.net/problem/2316

 

2316번: 도시 왕복하기 2

N개의 도시가 P개의 양방향 길로 연결되어 있다. 이석원은 1번 도시와 2번 도시 사이를 오가며 워해머를 한다. 성실한 이석원은 두 도시 사이를 최대한 많이 왔다 갔다 하려 하는데, 이때 한 번 방

www.acmicpc.net

도시 왕복하기 1과는 달리 이번에는 양방향 길입니다. 또한, 한 번 방문한 도시는 다시 방문하면 안됩니다.

이번에는 단순히 역방향 길에 해당하는 용량을 설정해주면 쉽게 풀릴 줄 알았으나, 결과는 실패였습니다.

 

어떻게 푸는지 도통 감을 못잡다가 결국 검색을 통해서, '정점 분리'라는 테크닉을 사용해서 풀 수 있다는 것을 알았습니다. '정점 분리'는 하나의 정점을 들어오는 정점(in)과 나가는 정점(out)으로 나누는 테크닉입니다. 그리고 in-out 사이에는 용량이 1인 간선(유향, in->out)을 추가합니다. 따라서, 1번 도시에서 2번 도시로 갈 때, 방문한 어느 한 정점에서 in-out 사이의 간선의 용량을 사용하게 되므로, 다른 경로는 이 정점을 통과하지 못하게 됩니다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

const int INF = 123456789;

void set_graph(std::vector<std::vector<int>>& graph, const int u, const int v, const int c)
{
    graph[u][v] = c;
    //graph[v][u] = -c;
}

bool bfs(const int s, const int t, const int n, const std::vector<std::vector<int>>& graph, std::vector<int>& prev, std::vector<bool>& visited)
{
    // init value
    for (int i = 0; i < n; i++)
        visited[i] = false;

    // create a queue for BFS
    std::queue<int> q;

    // mark s node as visited and enqueue it
    q.push(s);
    visited[s] = true;

    int u{};
    while (!q.empty()) {
        u = q.front();
        q.pop();

        // get adjacent vertices
        for (int v = 0; v < n; v++) {
            if (visited[v] == false && graph[u][v] > 0) {
                q.push(v);
                visited[v] = true;
                prev[v] = u;
            }
        }
    }

    return visited[t];
}

int edmonds_karp(const int source, const int sink, const int n, std::vector<std::vector<int>>& graph)
{
    std::vector<bool> visited;
    std::vector<int> prev;

    // init value
    visited.resize(n, false);
    prev.resize(n, -1);

    int max_flow{ 0 };

    int path_flow{}, s{}, u{}, v{};
    while (bfs(source, sink, n, graph, prev, visited)) {
        path_flow = INF;

        // find minimum capacity of the edges along the path by BFS
        s = sink;
        while (s != source) {
            path_flow = std::min(path_flow, graph[prev[s]][s]);
            s = prev[s];
        }

        // add path flow to overall flow
        max_flow += path_flow;

        // update residual copacities of the edges and reverse edges along the path
        v = sink;
        while (v != source) {
            u = prev[v];
            graph[u][v] -= path_flow;
            graph[v][u] += path_flow;
            v = prev[v];
        }
    }

    return max_flow;
}

int main(int argc, char* argv[])
{
    std::vector<std::vector<int>> graph;
    // set graph
    int n{}, p{};
    scanf("%d %d", &n, &p);
    graph.resize(2*n, std::vector<int>(2*n, 0)); // 각 정점을 in, out 2개로 분리

    int u, v;
    // in-out 정점 사이의 용량 1의 간선 추가
    for (int i = 0; i < n; i++) {
        u = 2 * i, v = u + 1;
        set_graph(graph, u, v, 1);
    }
    for (int i = 0; i < p; i++) {
        scanf("%d %d", &u, &v);
        u -= 1; v -= 1;
        u *= 2; v *= 2;
        set_graph(graph, u+1, v, 1);
        set_graph(graph, v + 1, u, 1);
    }

    // start
    auto result = edmonds_karp(1, 2, 2*n, graph);
    std::cout << result << "\n";
}

'Data Structure & Algorithm > 알고리즘' 카테고리의 다른 글

강한 연결 요소 (Strongly Connected Component)  (0) 2022.04.22
이분 매칭 (Bipartite Matching)  (0) 2022.04.21
선형 계획법과 치환 (3) - 쌍대성, 심플렉스법  (0) 2022.04.19
선형 계획법과 치환 (2) - Network Flow, Bipartite Matching  (0) 2022.04.17
선형 계획법과 치환 (1) - Examples of LP  (0) 2022.04.16

관련글

댓글

​

티스토리툴바