Algorithm/알고리즘 스터디(2021.07)
[Algorithm] 네트워크 플로우 (Network Flow)
binaryJournalist
2021. 10. 25. 00:14
반응형
인프런 29강에 대한 리뷰이다.
알고리즘의 개요와 실습 환경 구축 - 인프런 | 학습 페이지
지식을 나누면 반드시 나에게 돌아옵니다. 인프런을 통해 나의 지식에 가치를 부여하세요....
www.inflearn.com
네트워크 플로우는 특정한 지점에서 다른 지점으로 데이터가 얼마나 많이 흐르고 있는가를 측정하는 알고리즘이다.
표현 방식은 유랑/용량이다.
정체 현상없이 최대 유량을 보내야 한다. (최대 유량 문제, Max Flow)
최대 유량 문제는 각 간선에 정해진 용량이 있을 때 A에서 B로 최대로 보낼 수 있는 유량의 크기를 구하는 문제이다.
최대 유량 계산은 BFS를 이용하는 것이 일반적이고 이를 에드몬드 카프(Edmonds-Karp) 알고리즘이라고 한다.
(단순하게 모든 경우의 수를 탐색)
가능한 모든 경우의 수를 탐색하기 유량을 0으로 설정하고 유량/용량으로 표시한다.
용량 내 가능한 용량의 양을 반복적으로 더하면 된다.
최대 유량 알고리즘의 핵심적인 부분은 음의 유량을 계산하는 것이다.
가능한 한 모든 경로를 다 계산하기 위해 음의 유량을 계산하는데 다시 말하면 반대로 가는 유량이 빠지는 것이다.
남아있는 경로를 더 찾아내기 위해서다.
** 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
반응형