[c++] 최대 유량 문제 해결 알고리즘

08 Dec 2023

최대 유량 문제(Max Flow Problem)는 네트워크 상에서 한 지점에서 다른 지점으로 유량(flow)을 최대로 보낼 때, 최대로 보낼 수 있는 유량의 크기를 찾는 문제입니다.

최대 유량 문제를 해결하는 알고리즘으로는 대표적으로 Ford-Fulkerson 알고리즘이 있습니다. 이 알고리즘은 임의의 경로를 따라 순간적으로 흐를 수 있는 유량을 최대한 보내는 방법으로 동작합니다.

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

#define V 6

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;

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

        for (int v = 0; v < V; v++) {
            if (visited[v] == false && rGraph[u][v] > 0) {
                if (v == t) {
                    parent[v] = u;
                    return true;
                }
                q.push(v);
                parent[v] = u;
                visited[v] = true;
            }
        }
    }
    return false;
}

int fordFulkerson(int graph[V][V], int s, int t) {
    int u, v;
    int rGraph[V][V]; 
    for (u = 0; u < V; u++) {
        for (v = 0; v < V; v++) {
            rGraph[u][v] = graph[u][v];
        }
    }
    int parent[V];
    int max_flow = 0;

    while (bfs(rGraph, s, t, parent)) {
        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) << endl;

    return 0;
}

Ford-Fulkerson 알고리즘은 네트워크 플로우 문제를 풀이하는 데에 있어서 광범위하게 활용되고 있으며, 효율적인 최대 유량을 찾는데 사용됩니다.

참고 자료