디닉 알고리즘(Dinic's Algorithm)

디닉 알고리즘은 Maximum flow를 구하는 알고리즘 중에서 이분 그래프같은 특수한 환경에서 사용되는 알고리즘을 제외하고는 현재 PS분야에서 가장 빠르게 동작하는 알고리즘 입니다.

대부분의 유량 문제가 에드몬드 카프를 이용하여 해결 가능하지만 최근 몇몇 문제들은 디닉을 사용하지 않으면 시간초과를 보게 되는 경우도 많기 때문에 마음 편하게 디닉을 쓰시는걸 추천드립니다.

디닉 알고리즘의 시간 복잡도는 O(V^2*E)입니다.

그러면 디닉 알고리즘은 어떤 원리로 동작할까요? 

우선 BFS를 이용하여 잔여용량이 0 이상인 간선에 대하여 레벨 그래프(level graph)라는 것을 만들어줍니다

잔여용량(residual capacity)이란 플로우에서 해당

 간선의 기존 용량(c)에서 소스에서 흘려보낸 용량(f)를 뺀 값입니다. 즉 잔여용량이 1이상인 간선은 플로우가 아직 흐를수 있는 간선입니다.

레벨 그래프(level graph)는 각 정점들의 소스에서부터의 최단 거리에 대하여 레벨 값을 할당한 그래프 입니다. 소스의 레벨은 0이되고 소스와 인접한 정점의 레벨은 1 이후는 2... 가 되겠군요

위의 그림은 위키에서 가져왔는데 참고하시면 될 것 같습니다. 

왼쪽은 기존 그래프의 상태 중간은 잔여 용량 오른쪽은 레벨 그래프의 레벨을 매겨준 상태입니다. 오른쪽 그래프에서 유량이 흐르는 건 일단 무시하고 우선은 레벨값만 참고해주세요

bool bfs(){
    memset(level, -1, sizeof(level));        //레벨 그래프 초기화
    queue<int> qu;
    level[S] = 0;
    qu.push(S);        //S는 소스를 의미한다.
    while (qu.size()){
        int here = qu.front();
        qu.pop();
        for (auto i : vt[here]) {
            int there = i.v;
            int cap = i.cap;
            if (level[there] == -1 && cap > 0) {    //레벨이 아직 정해지지 않았고 잔여용량이 0이상
                level[there] = level[here] + 1;    //현재의 레벨값+1을 할당해준다.
                qu.push(there);
            }
        }
    }
    return level[E] != -1;    //E는 싱크를 의미한다. 싱크의 레벨이 할당이 안된 경우 0을 리턴
}

BFS의 소스코드는 위와 같이 됩니다.

이후 차단 유량(blocking flow)라는 개념을 이용하여 유량을 흘려보내주는데요. 디닉 알고리즘에서는 소스에서 싱크로 유량을 흘려줄 때 레벨 그래프에서의 차이가 딱 1만큼 클 때만 유량을 흘려줄 수 있습니다. 이때 DFS를 이용하여 유량을 최대로 흘려주면 됩니다.

이후 차단 유량만큼 간선의 용량을 줄여주고 역방향 간선에 차단 유량만큼 용량을 확장시켜 주면 됩니다.

DFS는 더 이상 흘릴 수 있는 유량이 없을 때 까지 탐색됩니다.

아까 그림에서의 오른쪽과 같이 되겠군요.

이후 간선의 용량을 변경해줍니다.

vector<vector<Edge>> vt;
struct Edge {
    int v, cap, rev;
    Edge(int v, int cap, int rev) :v(v), cap(cap), rev(rev) {}
};    //간선 구조체 , 반대쪽에 연결 된 정점과 용량 역방향 간선의 위치를 가지고있다. 
 
void addEdge(int s,int e,int c){
    vt[s].emplace_back(e, c, (int)vt[e].size());
    vt[e].emplace_back(s, 0, (int)vt[s].size() - 1);
}    //벡터의 사이즈 만큼을 넣어주어 역방향 간선의 위치를 저장한다.
 
int dfs(int here, int crtcap) {
    if (here == E)return crtcap;        //싱크일 경우 현재 흐르는 유량을 return 
    for (int &i = work[here]; i < vt[here].size(); i++) {    //work 배열에는 다음 탐색 위치가 저장되어 있다.
        int there = vt[here][i].v;
        int cap = vt[here][i].cap;
        if (level[here] + 1 == level[there] && cap>0) {    //레벨 그래프가 1만큼 크고 잔여 용량이 0 이상인 간선
            int c= dfs(there, min(crtcap, cap));        //dfs로 다음 위치 탐색
            if (c> 0) {        //싱크까지 도달하여 흐르는 차단유량이 0 이상일 경우 
                vt[here][i].cap -= c;    //현재 용량에서 차단 유량만큼을 빼줌
                vt[there][vt[here][i].rev].cap += c;    //역방향 간선에 c만큼 용량을 추가해줌
                return c;
            }
        }
    }
    return 0;
}

DFS 소스코드입니다.

자 위의 그림에서 우리는 현재 소스에서 싱크까지 14만큼의 유량이 흐르고 있는걸 알고 있습니다. 여기서 끝일까요? 

아닙니다 우리는 이제 또 현재 변경 된 그래프에 대해서 다시 BFS를 호출하여 새롭게 레벨 그래프를 형성해준 뒤 다시 dfs를 돌려서 유량을 뽑아내줍니다.

이를 레벨 그래프가 싱크까지 만들어 지지 않을 때까지 반복해줍니다.

이렇게 레벨 그래프를 새로 형성해 준 뒤 차단유량을 흘려주면 됩니다.

이후 간선의 용량을 변경 시켜 준 뒤 bfs를 돌려서 레벨 그래프가 만들어지지 않을 경우 함수를 종료합니다.

이 그래프에서의 최대유량(Maximum flow)는 14+5 = 19가 되겠군요.

이해를 좀 더 돕기 위해 BOJ 6086 최대 유량 소스코드를 첨부하겠습니다.

#include <cstdio>
#include <algorithm>
#include <string>
#include <queue>
#include <cstring>
#include <vector>
#include <iostream>
#define INF 987654321
#define S 0
#define E 25
#define MAX_A 60
using namespace std;
int n, z;
char x, y;
int level[MAX_A];
int work[MAX_A];
struct Edge {
    int v, cap, rev;
    Edge(int v, int cap, int rev) :v(v), cap(cap), rev(rev) {}
};    //간선 구조체 , 반대쪽에 연결 된 정점과 용량 역방향 간선의 위치를 가지고있다. 
vector<vector<Edge>> vt;
void addEdge(int s,int e,int c){
    vt[s].emplace_back(e, c, (int)vt[e].size());
    vt[e].emplace_back(s, 0, (int)vt[s].size() - 1);
}    //벡터의 사이즈 만큼을 넣어주어 역방향 간선의 위치를 저장한다.
 
bool bfs(){
    memset(level, -1, sizeof(level));        //레벨 그래프 초기화
    queue<int> qu;
    level[S] = 0;
    qu.push(S);        //S는 소스를 의미한다.
    while (qu.size()){
        int here = qu.front();
        qu.pop();
        for (auto i : vt[here]) {
            int there = i.v;
            int cap = i.cap;
            if (level[there] == -1 && cap > 0) {    //레벨이 아직 정해지지 않았고 잔여용량이 0이상
                level[there] = level[here] + 1;    //현재의 레벨값+1을 할당해준다.
                qu.push(there);
            }
        }
    }
    return level[E] != -1;    //E는 싱크를 의미한다. 싱크의 레벨이 할당이 안된 경우 0을 리턴
}
 
int dfs(int here, int crtcap) {
    if (here == E)return crtcap;        //싱크일 경우 현재 흐르는 유량을 return 
    for (int &i = work[here]; i < vt[here].size(); i++) {    //work 배열에는 다음 탐색 위치가 저장되어 있다.
        int there = vt[here][i].v;
        int cap = vt[here][i].cap;
        if (level[here] + 1 == level[there] && cap>0) {    //레벨 그래프가 1만큼 크고 잔여 용량이 0 이상인 간선
            int c= dfs(there, min(crtcap, cap));        //dfs로 다음 위치 탐색
            if (c> 0) {        //싱크까지 도달하여 흐르는 차단유량이 0 이상일 경우 
                vt[here][i].cap -= c;    //현재 용량에서 차단 유량만큼을 빼줌
                vt[there][vt[here][i].rev].cap += c;    //역방향 간선에 c만큼 용량을 추가해줌
                return c;
            }
        }
    }
    return 0;
}
 
int main(){
    scanf("%d", &n);
    vt.resize(MAX_A);
    for (int i = 0; i < n; i++){
        cin >> x >> y;
        scanf("%d", &z);
        int a, b;
        if ('A' <= x&&x <= 'Z')
            a = x - 'A';
        else
            a = x - 'a' + 26;
        if ('A' <= y&&y <= 'Z')
            b = y - 'A';
        else
            b = y - 'a' + 26;
        addEdge(a, b, z);
    }
    int res = 0;
    while (bfs()){    //레벨 그래프가 만들어 지는 경우에만 동작
        memset(work, 0, sizeof(work));
        while (1){
            int flow = dfs(S, INF);    //차단유량을 구하여
            if (!flow)break;    
            res += flow;    //차단유량이 1이상일 경우 maximum flow에 더해줌
        }
    }
    printf("%d", res);
    return 0;
}
 

자 이제 디닉 알고리즘을 이용하여 여러가지 유량 문제를 풀어봅시다.