Dinic's Algorithm

http://blog.naver.com/kks227/220812858041

디닉 알고리즘(Dinic's Algorithm) (수정: 2016-09-19)

kks227님의 디닉알고리즘 코드와 설명을 참고했습니다!

 

//디닉 알고리즘
 
int capa[MAX_V][MAX_V], flow[MAX_V][MAX_V];
//레벨 그래프에서 정점의 레벨(S가 0)
int level[MAX_V];
//dfs 중, 이 정점이 몇 번째 간선까지 탐색했는지 기억하는 용도
int work[MAX_V];
vector<int> adj[MAX_V];
 
//디닉 전용 bfs 함수
bool bfs()
{
    //레벨값 초기화
    fill(level, level+MAX_V, -1);
    level[S] = 0;
 
    queue<int> Q;
    Q.push(S);
    while(!Q.empty())
    {
        int curr = Q.front();
        Q.pop();
        for(int next : adj[curr])
            //레벨값이 설정되지 않았고, 간선에 residual이 있을 때만 이동
            if(level[next] == -1 && capa[curr][next] - flow[curr][next] > 0)
            {
                level[next] = level[curr] + 1;
                Q.push(next);
            }
    }
    //싱크에 도달 가능하면 true, 아니면 false를 리턴
    return level[E] != -1;
}
 
//디닉 전용 dfs 함수: curr에서 dest까지 최대 flow만큼의 유량을 보낼 것
int dfs(int curr, int dest, int flow)
{
    //base case: dest에 도달함
    if(curr == dest) return flow;
 
    //현재 정점에서 인접한 정점등를 탐색
    //이때, 이번 단계에서 이미 쓸모없다고 판단한 간선은 다시 볼 필요가 없으므로
    //work 배열로 간선 인덱스를 저장해 둠
    //++i 가 아닌 i++를 해야함!
    //왜냐하면 return df를 하고 나서 같은 레벨 그래프의
    //다음 dfs에서 해당 간선을 다시 사용할수 있기 때문에 
    //return df가 되어 i가 증가하지 않도록 해야함!
    for(int& i = work[curr]; i<adj[curr].size(); i++)
    {
        int next = adj[curr][i];
        //next의 레벨이 curr의 레벨+1 이고, 간선에 residual이 남아있어야만 이동
        if(level[next] == level[curr]+1 && capa[curr][next] - flow[curr][next] > 0)
        {
            //df: flow와 다음 dfs함수의 결과 중 최소값
            //결과적으로 경로상의 간선들 중 가장 작은 residual이 됨
            int df = dfs(next, dest, min(capa[curr][next] - flow[curr][next], flow));
            //증가 경로가 있다면, 유량을 df만큼 흘리고 종료
            if(df > 0)
            {
                flow[curr][next] += df;
                flow[next][curr] -= df;
                return df;
            }
        }
    }
    //증가 경로를 찾지 못함: 유량 0 흘림
    return 0;
}
 
int main()
{
    //디닉 알고리즘 수행
    int total = 0;
    //레벨 그래프를 구축하여 싱크가 도달 가능한 동안 반복
    while (bfs())
    {
        fill(work, work+MAX_V, 0);
        //차단 유량(blocking flow) 구하기
        while(1)
        {
            //dfs를 사용해 각 경로를 찾음
            int flow = dfs(S, E, INF);
            //더 이상 경로가 없으면 종료
            if(flow == 0) break;
            //총 유량에 이번에 구한 유량 더함
            total += flow;
        }
    }
    //전체 유량 출력
    printf("%d\n", total);
}

 

 

 

 

 

 

Dinic's Algorithm

최대 유량 알고리즘 입니다! 이전에 소개한 Ford-Fulkerson algorithm 보다 더 빠른 시간복잡도를 가지는 알고리즘 입니다.

 

디닉 알고리즘에 사용되는 두가지 용어 입니다.

 

1. 레벨 그래프(level graph) : 시작 정점의 레벨이 0, 그리고 그와 인접한 정점의 레벨이 1, 레벨 1 정점과 인접한 정점의 레벨이 2.... 이런식으로 정점의 레벨을 붙여 만든 그래프 입니다.

 

2. 차단 유량(blocking flow) : 디닉 알고리즘에선 유량을 보낼때, 간선 (u, v)에서 level[u] + 1 = level[v]를 만족 할때만 유량을 보낼수 있습니다. 위의 조건을 만족하면서 유량을 보낼때 해당 레벨 그래프에서 더이상 source에서 sink로 유량을 보낼수 없을 때까지 최대한 보낸 유량을 차단 유량이라고 합니다.

 

즉 디닉 알고리즘은

1. 레벨 그래프를 만든다.

2. 만들어진 레벨 그래프에서 차단 유량만큼 유량을 흘려보내준다.

 

위의 두 과정을 레벨 그래프에서 sink에 도달하지 못할때까지 반복해 줍니다. 그리고 이때 흘려보낸 유량의 합이 source에서 sink로 보낼 수 있는 최대 유량이 됩니다.

 

 

 

 

 

 

시간복잡도

O(|V|^2*|E|)