포드 풀커슨 알고리즘

최단 경로 문제에서는 정점 간 간선의 가중치의 합이 최소가 되는 경로의 길이를 찾으려 했습니다.

 

네트워크 플로우는 시작점에서 도착점까지 유량을 최대로 흘려보내는 것이 목적입니다.

어떻게 보면 가중치의 합을 최대로 만드는 것인데 여기서 용량이라는 개념이 추가됩니다.

 

 

네트워크 유량은 항상 3가지 규칙을 만족해야 합니다.

 

1. 용량 제한 속성 flow(u,v) <= capacity(u,v) : 간선의 유량은 간선의 용량을 초과할 수 없다.

2. 유량의 대칭성  flow(u,v) = -flow(v,u)       : u가 v에게 보낸 유량은 v가 u에게 음의 유량을 보낸 것과 같다.

3. 유량의 보존     ∑flow(u,v) = 0               : 시작점과 도착점을 제외한 정점에서 보낸 유량과 나간 유량은 같다.         

 

이 문제를 풀기위한 대표적인 알고리즘으로는 포드-풀커슨 알고리즘, 디닉 알고리즘 등이 있습니다.

 

이번 포스팅에선 포드-풀커슨 알고리즘에 대하여 알아볼 것입니다.

그럼 동작 과정을 살펴봅시다.

---

간선 당 용량을 입력받은 상태입니다. 초기 유량은 전부 0으로 초기화된 모습입니다.

 

네트워크 유량 문제에서는 시작점을 소스, 도착점을 싱크라고 부릅니다.

1번 노드를 소스, 4번 노드를 싱크로 고려하고 유량을 보내는 경로인 증가 경로(Augmenting Path) 를 찾아보겠습니다.

 

소스부터 싱크까지 증가 경로를 찾아가봅니다. (1-2-3-4)

증가 경로를 따라 흘려보내는 유량은 경로 상 간선의 잔여 용량 최소치로 결정됩니다.

간선의 잔여 용량은 간선의 용량에서 유량을 뺀 값입니다.

 

residual(1,2) = capacity(1,2) - flow(1,2) = 1 - 0 = 1

residual(2,3) = capacity(2,3) - flow(2,3) = 1 - 0 = 1

residual(3,4) = capacity(3,4) - flow(3,4) = 2 - 0 = 2

 

이 중에서 최소치인 1만큼 증가 경로를 타고 소스에서 싱크까지 흘려보냅니다.

 

 

소스부터 싱크까지 증가 경로를 찾아가봅니다. (1-3-4)

 

residual(1,3) = capacity(1,3) - flow(1,3) = 3 - 0 = 3

residual(3,4) = capacity(3,4) - flow(3,4) = 2 - 1 = 1

 

이 중에서 최소치인 1만큼 증가 경로를 타고 소스에서 싱크까지 흘려보냅니다.

 

소스부터 싱크까지 증가 경로를 찾아가봅니다.

소스에서 유량이 흐를 수 있는 경로는 (1-3) 이 있지만 capacity(3,2) =0 , residual(3,4) = 0 이라서 증가 경로가 없을 것 같습니다. 정말 증가 경로는 더 이상 찾을 수 없는 것일까요?

 

여기서 유량의 대칭성이 힘을 발휘합니다. flow(3,2) = -flow(2,3) = -1

잔여 용량을 확인해봅시다. residual(3,2) = capacity(3,2) - flow(3,2) = 0 -(-1) = 1

용량 제한 속성을 보면 flow(3,2) <= capacity(3,2) 도 성립합니다.

capacity(3,2) = 0 이기 때문에 유량을 흘려보낼 수 없을 것 같지만 flow(2,3) 와 flow(3,2)을 상쇄 시킨다면 어떨까요.

 

네트워크 유량의 법칙을 만족시키면서 증가 경로를 하나 더 찾을 수 있는 셈입니다. (1-3-2-4)

 

포드-풀커슨 알고리즘의 과정을 다시 정리해봅시다.

 

1. 각 간선의 용량을 입력받습니다.

2. DFS 또는 BFS 를 이용하여 증가 경로를 찾습니다.

3. 증가 경로 상의 간선 중 잔여 용량이 가장 낮은 것을 찾습니다.

4. 잔여 용량 최소치만큼 소스에서 싱크까지 유량을 흘려보냅니다.

5. 더 이상 증가 경로가 발견이 되지 않을 때까지 반복합니다.

 

 

이 포스팅에서는 BFS 를 이용하여 포드-풀커슨 알고리즘을 소스코드로 알아보겠습니다.

BFS 를 이용할 때, 포드-풀커슨 알고리즘은 특별히 에드몬드-카프 알고리즘으로 불립니다.

---

#define MAX 987654321
int V,E,u,v,c;

int cap[V_Max][V_Max],flow[V_Max][V_Max];
//간선의 용량과 유량을 저장할 배열을 생성합니다.

int ford(int src,int sink){

	int res;
    //반환할 최대 유량값입니다.
    
    while(true){
    //싱크에 유량을 보내는 일이 없을 때까지, 즉, 증가 경로가 없을 때까지 반복합니다.
    
    	vector<int>parent(V_Max,-1);
        //어느 정점에서 유량이 흘러왔는지 저장할 벡터를 생성합니다.
        //-1에서 값이 바뀐다면 유량이 흘러들어온 것입니다.
        
    	queue <int> q;
        //유량을 흘려보낼 정점을 보관할 큐를 생성합니다.
        
    	q.push(src);parent[src]=src; 
        //소스를 큐에 넣습니다. 
        
        while(!q.empty() && parent[sink]==-1){
        //방문할 정점이 존재하고 아직 싱크에 도달하지 않았다면 반복합니다
        
        	int here = q.front(); q.pop();
            //큐에서 방문할 정점을 하나 뽑습니다.
            
        	for(int there =0;there<V;there++){
            //모든 정점에 대하여
            
            	if(cap[here][there]-flow[here][there] >0 && parent[there]==-1)
                	q.push(there); parent[there]=here;
                //잔여 용량이 있고 아직 방문하지 않았다면, 큐에 넣고 방문처리를 합니다.
            }
        }
        
     	if(parent[sink]==-1)break;
        //싱크에 도착하지 않았다면 반복을 그만둡니다.
        
        int amount=MAX;
        //흘려보낼 유량이 얼마나 되는지 저장합니다.
        
        for(int vertex=sink;vertex!=src;vertex=parent[vertex])
        	amount=min(cap[parent[vertex]][vertex]-flow[parent[vertex]][vertex],amount);
        //증가 경로의 간선 중에서 잔여 용량이 가장 작은 것을 유량으로 고려합니다.
            
        for(int vertex=sink;vertex!=src;vertex=parent[vertex]){
        	flow[parent[vertex]][vertex]+=amount;
            flow[vertex][parent[vertex]]-=amount;
        }
        //흘러오는 유량과 보내는 유량을 각 간선마다 갱신합니다.
        
        res+=amount;
        //증가 경로를 통한 유량을 총 유량에 추가합니다.
        
    }
	return res;
    //계산된 최대 유량을 반환합니다.
}

---

포드-폴커슨 알고리즘의 시간 복잡도

 

포드-풀커슨 알고리즘의 시간 복잡도는 반복문 관점에서 계산하지 않습니다.

 

최대 유량이 f 라면 각 증가 경로 당 유량이 최소 1 이기 때문에 증가 경로의 최대 개수는 f 가 됩니다.

하나의 증가 경로를 찾는데 방문하는 정점과 간선은 최대로 계산할 시, 각각 V, E 개 입니다.

따라서 최대 유량을 얻어내는데 필요한 시간 복잡도는 O((|E|+|V|)f) 입니다.

정점의 개수가 무시할 만큼 작다면 O(|E|f) 가 되겠습니다.

 

만약 BFS 를 이용한다면 f 를 탐색하는데 |E||V| 가 소요되어 시간 복잡도는 O(|V||E|^2) 가 됩니다.

따라서 포드-풀커슨 알고리즘의 시간 복잡도는 O(|V||E|^2) 와 O(|E|f) 중 작은 값이 됩니다.

---

연습문제

 

 

 

 

네트워크 플로우의 포드-풀커슨 알고리즘에 대한 포스팅이었습니다.

 

오타 지적과 조언은 언제나 환영입니다.