[Algorithm] 네트워크 플로우 (Network Flow)

 

 

인프런 29강에 대한 리뷰이다.

 

https://www.inflearn.com/course/algorithm-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%8B%A4%EC%8A%B5/lecture/12358

알고리즘의 개요와 실습 환경 구축 - 인프런 | 학습 페이지

 

네트워크 플로우는 특정한 지점에서 다른 지점으로 데이터가 얼마나 많이 흐르고 있는가를 측정하는 알고리즘이다.

 

표현 방식은 유랑/용량이다.

 

정체 현상없이 최대 유량을 보내야 한다. (최대 유량 문제, Max Flow)

최대 유량 문제는 각 간선에 정해진 용량이 있을 때 A에서 B로 최대로 보낼 수 있는 유량의 크기를 구하는 문제이다.

 

 

 

출처: https://blog.naver.com/ndb796/221237111220

 

최대 유량 계산은 BFS를 이용하는 것이 일반적이고 이를 에드몬드 카프(Edmonds-Karp) 알고리즘이라고 한다.

(단순하게 모든 경우의 수를 탐색)

 

https://blog.naver.com/ndb796/221237111220

 

 

가능한 모든 경우의 수를 탐색하기 유량을 0으로 설정하고 유량/용량으로 표시한다.

용량 내 가능한 용량의 양을 반복적으로 더하면 된다.

 

최대 유량 알고리즘의 핵심적인 부분은 음의 유량을 계산하는 것이다.

가능한 한 모든 경로를 다 계산하기 위해 음의 유량을 계산하는데 다시 말하면 반대로 가는 유량이 빠지는 것이다.

남아있는 경로를 더 찾아내기 위해서다.

 

 

출처: https://blog.naver.com/ndb796/221237111220

 

 

 

** C++

 

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

#define MAX 100
#define INF 1000000000

using namespace std;
int n = 6, result;
int c[MAX][MAX], f[MAX][MAX], d[MAX];
vector<int> a[MAX];

void maxFlow(int start, int end) {
	while(1) {
		fill(d, d + MAX, -1);
		queue<int> q;
		q.push(start);
		while(!q.empty()) {
			int x = q.front();
			q.pop();
			for (int i = 0; i < a[x].size(); i++) {
				int y = a[x][i];
				// 방문하지 않은 노드 중에 용량이 남은 경우
				if (c[x][y] - f[x][y] > 0 && d[y] == -1) {
					q.push(y);
					d[y] = x; // 경로를 기억함  
					if (y == end) break; // 도착지에 도달한 경우 
				} 
			}
		}
		// 모든 경로를 찾은 뒤에 탈출  
		if (d[end] == -1) break;
		int flow = INF;
		 // 반대방향으로 최소 유량 탐색 
		for (int i = end; i != start; i = d[i]) {
			flow = min(flow, c[d[i]][i] - f[d[i]][i]);
		}
		// 최소 유량만큼 추가
		for (int i = end; i != start; i = d[i]) {
			f[d[i]][i] += flow;
			f[i][d[i]] -= flow;
		} 
		result += flow;
	} 
}

int main(void) {
	a[1].push_back(2);
	a[2].push_back(1);
	c[1][2] = 12;
	
	a[1].push_back(4);
	a[4].push_back(1);
	c[1][4] = 11;
	
	a[2].push_back(3);
	a[3].push_back(2);
	c[2][3] = 6;

	a[2].push_back(4);
	a[4].push_back(2);
	c[2][4] = 3;
	
	a[2].push_back(5);
	a[5].push_back(2);
	c[2][5] = 5;
	
	a[2].push_back(6);
	a[6].push_back(2);
	c[2][6] = 9;
	
	a[3].push_back(6);
	a[6].push_back(3);
	c[3][6] = 8;
	
	a[4].push_back(5);
	a[5].push_back(4);
	c[4][5] = 9;
	
	a[5].push_back(3);
	a[3].push_back(5);
	c[5][3] = 3;
	
	a[5].push_back(6);
	a[6].push_back(5);
	c[5][6] = 4;
	
	maxFlow(1, 6);
	printf("%d", result);
}

 

 

 

** Python

 

 

수정 전: 18 -> 21 로 나옴

 

from collections import deque

totalFlow = 0
MAX_V = 100
INF = 1000000000
 
N = 6
capacity = [[0] * MAX_V for _ in range(MAX_V)]
flow = [[0] * MAX_V for _ in range(MAX_V)]
adjList = [[] for _ in range(MAX_V)]

arr = [[1, 2, 12], [1, 4, 11], [2, 3, 6], [2, 4, 3], [2, 5, 5],
    [2, 6, 6], [3, 6, 8], [4, 5, 9], [5, 3, 3], [5, 6, 4]] ## 2, 6, 6 => 2, 6, 9
    
for sv, dv, c in arr:
    capacity[sv][dv] += int(c)
    capacity[dv][sv] += int(c)
    adjList[sv].append(dv)
    adjList[dv].append(sv)

def BFS(source, sink, visit):
    dq = deque()
    dq.append(source)
    
    while dq and visit[sink] == -1:
        sv = dq.popleft()
 
        for dv in adjList[sv]:
            if capacity[sv][dv] - flow[sv][dv] > 0 and visit[dv] == -1:
                dq.append(dv)
                visit[dv] = sv
 
                if dv == sink:
                    break
        
    if visit[sink] == -1:
        return True
    else:
        return False
 

def edmondsKarp(source, sink):
    while 1:
        visit = [-1] * MAX_V
        if BFS(source, sink, visit):
            break
 
        minFlow = INF
        
        i = sink
        while i != source:
            minFlow = min(minFlow, capacity[visit[i]][i] - flow[visit[i]][i])
            i = visit[i]
        
        i = sink
        while i != source:
            flow[visit[i]][i] += minFlow
            flow[i][visit[i]] -= minFlow
            i = visit[i]
        
        global totalFlow
        totalFlow += minFlow
    
    return totalFlow
 
source = 1
sink = 6
 
print(edmondsKarp(source, sink))

 

수정 후

 

from collections import deque

totalFlow = 0
MAX_V = 100
INF = 1000000000
 
N = 6
capacity = [[0] * (N+1) for _ in range(N+1)]
flow = [[0] * (N+1) for _ in range(N+1)]
adjList = [[] for _ in range(N+1)]

arr = [[1, 2, 12], [1, 4, 11], [2, 3, 6], [2, 4, 3], [2, 5, 5],
    [2, 6, 9], [3, 6, 8], [4, 5, 9], [5, 3, 3], [5, 6, 4]]
    
for sv, dv, c in arr:
    capacity[sv][dv] = int(c)
    # capacity[dv][sv] = int(c)
    adjList[sv].append(dv)
    adjList[dv].append(sv)

# adjList[1].append(2)
# adjList[2].append(1) # 음의 유량
# capacity[1][2] = 12

# adjList[1].append(4)
# adjList[4].append(1) # 음의 유량
# capacity[1][4] = 11

# adjList[2].append(3)
# adjList[3].append(2) # 음의 유량
# capacity[2][3] = 6

# adjList[2].append(4)
# adjList[4].append(2) # 음의 유량
# capacity[2][4] = 3

# adjList[2].append(5)
# adjList[5].append(2) # 음의 유량
# capacity[2][5] = 5

# adjList[2].append(6)
# adjList[6].append(2) # 음의 유량
# capacity[2][6] = 9

# adjList[3].append(6)
# adjList[6].append(3) # 음의 유량
# capacity[3][6] = 8

# adjList[4].append(5)
# adjList[5].append(4) # 음의 유량
# capacity[4][5] = 9

# adjList[5].append(3)
# adjList[3].append(5) # 음의 유량
# capacity[5][3] = 3

# adjList[5].append(6)
# adjList[6].append(5) # 음의 유량
# capacity[5][6] = 4


def BFS(source, sink, visit):
    dq = deque()
    dq.append(source)
    
    while dq and visit[sink] == -1:
        sv = dq.popleft()
 
        for dv in adjList[sv]:
            if capacity[sv][dv] - flow[sv][dv] > 0 and visit[dv] == -1:
                dq.append(dv)
                visit[dv] = sv
 
                if dv == sink:
                    break
        
    if visit[sink] == -1:
        return True
    else:
        return False
 

def edmondsKarp(source, sink):
    while 1:
        visit = [-1 for i in range(MAX_V)]
        if BFS(source, sink, visit):
            break
 
        minFlow = INF
        
        i = sink
        while i != source:
            minFlow = min(minFlow, capacity[visit[i]][i] - flow[visit[i]][i])
            i = visit[i]
        
        i = sink
        while i != source:
            flow[visit[i]][i] += minFlow
            flow[i][visit[i]] -= minFlow
            i = visit[i]
        
        global totalFlow
        totalFlow += minFlow
    
    return totalFlow
 
source = 1
sink = 6
 
print(edmondsKarp(source, sink))

 

참고: https://hellominchan.tistory.com/354