[알고리즘 개념] Network Flow(네트워크 플로우) 최소 비용 최대 유량 (Minimum Cost Maximum Flow) Algorithm

해당 내용은 기본적인 Network Flow 알고리즘 중 하나인 Max Flow Algorithm을 기반으로 작성하였습니다.

2022.07.18 - [알고리즘 개념] Network Flow(네트워크 플로우) Edmonds-Karp Alogorithm

[알고리즘 개념] Network Flow(네트워크 플로우) Edmonds-Karp Alogorithm

MCMF 란?

MCMF(최소 비용 최대 유량) 알고리즘은 최대 유량을 사용하는 알고리즘상황에서 추가적으로 간선의 비용까지 조건에 포함하여 사용할 수 있는 알고리즘입니다. 즉 간선의 가중치를 거리라고 하였을 때, 최단 경로의 최대 유량을 구하는 알고리즘 이라고 할 수 있습니다.

MCMF 작동 원리

기본적으로 최소 비용을 구하여 그 최소 비용에 해당하는 간선으로부터 최대 유량을 구하는 알고리즘입니다.

이때 최소 비용이라는 뜻은 다시 해석하자면 최단 거리가 됩니다.

따라서 최단거리를 바탕으로 해당 최단거리에서의 최대 유량을 구하면 됩니다.

최단 거리를 구하고자 하는 알고리즘은 다양합니다.

1. 다익스트라 알고리즘 - 다익스트라 알고리즘 개념
2. 벨만 포드 알고리즘 - 벨만포드 알고리즘 개념
3. 플로이드 와샬 알고리즘 - 플로이드 워셜 알고리즘 개념
4. SPFA 알고리즘 - SPFA 알고리즘 개념
5. 기타 등등

최단 거리를 구하고자 할때 각 알고리즘의 특징 별로 다르게 적용하면 됩니다. 위 개념들은 추 후 제 블로그에 정리하여 다시 한번 올리도록 하겠습니다.

최단거리를 구할 때 음수의 가중치가 있을 수 있으므로 다익스트라 알고리즘이 아닌

벨만포드 알고리즘과 벨만포드 알고리즘을 향상시킨 SPFA 알고리즘을 접목시킨 MCMF에 대하여 설명 하도록 하겠습니다.

벨만포드와 SPFA 알고리즘을 통해 최소 비용을 구하게 됩니다. 이후 최대 유량을 구하므로 결과값은 경로 비용의 합 * 유량을 더해주면 됩니다.

이때 MCMF에서도 주의할 점이 있습니다.

그전 Network Flow algorithm중 하나인 Edmonds- Karp 알고리즘을 공부 할 때도 유량의 음의 간선을 생각하여 계산 하였습니다. 이번 MCMF에서는 유량을 흘릴 때 간선의 비용도 역방향으로 해줘야 합니다.즉 Cost(a,b)가 10이라면 , Cost(b,a)는 -10으로 생각 할 수 있습니다. 

이때 벨만 포드 알고리즘을 이용하여  MCMF 알고리즘을 진행 할땐 시간복잡도가 O(VE)가 걸리고,

SPFA알고리즘을 이용하여 MCMF 알고리즘을 진행 하면 표기상으론 O(VE)이지만 실제론 거의 O(V+E)가 걸립니다.

 

MCMF 코드 분석

해당 알고리즘을 공부하고자 해당 블로그의 코드를 분석하며 공부하였습니다.

https://cael0.github.io/problem%20solving/BOJ11405/

[BOJ 11405] 책 구매하기

 

 

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())  # 사람의 수 n , 온라임 서점의 수 m
a = list(map(int, sys.stdin.readline().split())) # 각 사람이 사려고 하는 책의 개수
b = list(map(int, sys.stdin.readline().split())) # 각 온라인 서점이 가지고 잇는 책의 개수
board = [list(map(int, sys.stdin.readline().split())) for _ in range(m)] # 온라인 서점이 각 사람들에게 책을 한권 보내는데 필요한 배송비
graph = [[] for _ in range(m + n + 2)] # start, end, 서점, 사람 수를 포함하여 graph를 만듬

for i in range(1, m + 1): # 초기 start지점에서 서점까지의 용량을 저장해놈
    graph[0].append([i, b[i - 1]])

    for j in range(m + 1, m + n + 1): # 서점에서 사람까지 보낼 수 있는 값을 무한대로 초기에 설정함.
        graph[i].append([j, float('inf')])

for j in range(m + 1, m + n + 1): # 사람에서 end포인트지점까지 사람이 사려고자 하는 책의 개수를 저장해놈.
    graph[j].append([m + n + 1, a[j - m - 1]])


weight = 0

while True:
    res = [float('inf')] * (m + n + 2)
    res[0] = 0

    prev = [-1] * (m + n + 2) # -1 * 10
    visit = [0] * (m + n + 2) # 0 * 10
    queue = deque([0])

    while queue: # SPFA 알고리즘 과정
        cur = queue.popleft()
        visit[cur] = 0 # 방문리스트 초기 cur인덱스 0으로 초기화

        for nxt, capacity in graph[cur]: # graph[초기] 안에 있는 값들 갖고오기. ex) [1,5],[2,3],[3,2],[4,1] nxt가 노드, capacity가 수용량
            if 0 < cur < nxt < m + n + 1: # 현재값이 탐색할 인덱스 값보다 작으면 cost 양의 간선
                cost = board[cur - 1][nxt - m - 1]
            elif 0 < nxt < cur < m + n + 1: # 현재값이 탐색할 인덱스 값보다 작으면 cost 음의 간선
                cost = -board[nxt - 1][cur - m - 1]
            else:
                cost = 0

            if res[cur] + cost < res[nxt] : #현재 값의 res와 cost를 더한 값이 현개 값의 인접노드 값보다 작을 때
                res[nxt] = res[cur] + cost # 다음 노드의 res 값을 현재 값 + cost로 바꿈
                prev[nxt] = cur   # prev의 인접 노드의 인덱스를 현재 cur값으로 바꿈

                if not visit[nxt]: # 만약 인접한 노드가 방문하지 않았을 때  que에 해당 값을 추가하고 방문을 체크함.
                    queue.append(nxt)
                    visit[nxt] = 1

    if res[-1] == float('inf'): # res의 마지막 인덱스가 inf면 break
        break

    flow = float('inf') #flow를 무한대로 설정  , Natwork Flow alglorithm
    nxt = m + n + 1 #nxt를  m+n+1 로 설정 마지막 사람.
    while nxt: #nxt가 0이 되기전까지 반목
        cur = prev[nxt] #prev[nxt]를 가져옴 이게 cur 변수 , 즉 특정 사람 인덱스
        for i in range(len(graph[cur])): #그래프의 cur인덱스 길이 만큼 반복문 실행
            if graph[cur][i][0] == nxt: #그래프의 cur 인덱스의
                flow = min(flow, graph[cur][i][1])
                break
        nxt = cur

    nxt = m + n + 1 # 사람 마지막 노드 번호
    while nxt:
        cur = prev[nxt] # 사람 마지막 노드번호에 인접한 노드를 가져옴

        if 0 < cur < nxt < m + n + 1: # 인접한 노드가 현재 번호 보다 작으면 양의 간선이므로 weight , 즉 가중치를 더함.
            weight += flow * board[cur - 1][nxt - m - 1]   # board = 배송비 , flow = 보내야 하는 노드
        elif 0 < nxt < cur < m + n + 1: # 인접한 노드가 현재 번호 보다 크면 반대 방향이라는 의미이므로 가중치를 뺌.
            weight -= flow * board[nxt - 1][cur - m - 1]

        for i in range(len(graph[cur])): # 인접 노드의 graph 즉, 인접 노드에서 몇개의 인접 노드가 있는지 반복문을 돔.
            if graph[cur][i][0] == nxt: # 인접 노드에 초기 탐색 한 노드가 있다면
                graph[cur][i][1] -= flow # 인접 노드에 음의 flow를 흘려보냄.
                if graph[cur][i][1] == 0: # 만약 인접 노드의 flow가 0이라면
                    graph[cur].remove([nxt, 0]) # 해당 인접 노드를 지움.  아마 자기 자신을 향한 그래프라 생각해서 그런거 같음.
                break

        for i in range(len(graph[nxt])): # graph의 현재 인접 개수 만큼 반복함
            if graph[nxt][i][0] == cur: # 현재 노드에서 인접한 노드가 있다면
                graph[nxt][i][1] += flow # 양의 flow를 흘려 보냄
                break
        else:
            graph[nxt].append([cur, flow]) # 인접 개수가 없다면 현재 그래프에 인접노드와 flow를 추가함.

        nxt = cur # 인접 노드가 현재 노드로 바뀜
print(graph)
print(board)
print(weight)

해당 코드의 전체적인 부분입니다.  코드 자체는 제가 태그를 걸어놓은 블로그분의 코드이며 해당 주석은 제가 코드를 분석하며 제가 생각한 부분을 작성해 놓은 것입니다. 코드를 분해하며 설명하도록 하겠습니다. 해당 코드는 MCMF 알고리즘이며 최단경로를 구하는 알고리즘은 SPFA (Shortest Path Faster Algorithm)을 사용하였습니다.

변수 세팅

n, m = map(int, sys.stdin.readline().split())  # 사람의 수 n , 온라임 서점의 수 m
a = list(map(int, sys.stdin.readline().split())) # 각 사람이 사려고 하는 책의 개수
b = list(map(int, sys.stdin.readline().split())) # 각 온라인 서점이 가지고 잇는 책의 개수
board = [list(map(int, sys.stdin.readline().split())) for _ in range(m)] # 온라인 서점이 각 사람들에게 책을 한권 보내는데 필요한 배송비
graph = [[] for _ in range(m + n + 2)] # start, end, 서점, 사람 수를 포함하여 graph를 만듬

for i in range(1, m + 1): # 초기 start지점에서 서점까지의 용량을 저장해놈
    graph[0].append([i, b[i - 1]])

    for j in range(m + 1, m + n + 1): # 서점에서 사람까지 보낼 수 있는 값을 무한대로 초기에 설정함.
        graph[i].append([j, float('inf')])

for j in range(m + 1, m + n + 1): # 사람에서 end포인트지점까지 사람이 사려고자 하는 책의 개수를 저장해놈.
    graph[j].append([m + n + 1, a[j - m - 1]])

알고리즘을 풀기 위해 초기 변수들을 세팅하는 부분입니다. 2중 for문 1개와 일반 for문 1개가 있습니다. 이 부분을 분석해봤더니 아래와 가같은 이미지가 나왔습니다.  s는 현재 시작 노드에서 서점까지의 capacity정보를 저장합니다. 이후 각 서점마다 각 사람들에 대하여 정보를 저장하게 합니다. 이때 최단거리를 사용하므로 초기값은 무한대로 설정합니다.  

해당 변수 세팅을 하고 나서 초기 graph 이미지화를 한 모습

input 값으로는 아래와 같이 해당 값을 넣었습니다. 

4 4
3 2 4 2
5 3 2 1
5 6 2 1
3 7 4 1
2 10 3 1
10 20 30 1

SPFA 알고리즘

이후 해당 부분은 SPFA 알고리즘이 동작하는 과정입니다.

while True:
    res = [float('inf')] * (m + n + 2)
    res[0] = 0

    prev = [-1] * (m + n + 2) # -1 * 10
    visit = [0] * (m + n + 2) # 0 * 10
    queue = deque([0])

    while queue: # SPFA 알고리즘 과정
        cur = queue.popleft()
        visit[cur] = 0 # 방문리스트 초기 cur인덱스 0으로 초기화

        for nxt, capacity in graph[cur]: # graph[초기] 안에 있는 값들 갖고오기. ex) [1,5],[2,3],[3,2],[4,1] nxt가 노드, capacity가 수용량
            if 0 < cur < nxt < m + n + 1: # 현재값이 탐색할 인덱스 값보다 작으면 cost 양의 간선
                cost = board[cur - 1][nxt - m - 1]
            elif 0 < nxt < cur < m + n + 1: # 현재값이 탐색할 인덱스 값보다 작으면 cost 음의 간선
                cost = -board[nxt - 1][cur - m - 1]
            else:
                cost = 0

            if res[cur] + cost < res[nxt] : #현재 값의 res와 cost를 더한 값이 현개 값의 인접노드 값보다 작을 때
                res[nxt] = res[cur] + cost # 다음 노드의 res 값을 현재 값 + cost로 바꿈
                prev[nxt] = cur   # prev의 인접 노드의 인덱스를 현재 cur값으로 바꿈

                if not visit[nxt]: # 만약 인접한 노드가 방문하지 않았을 때  que에 해당 값을 추가하고 방문을 체크함.
                    queue.append(nxt)
                    visit[nxt] = 1

    if res[-1] == float('inf'): # res의 마지막 인덱스가 inf면 break
        break

먼저 자기 시작 노드를 0으로 세팅하는 것을 제외하고는 다른 노드들을 전부다 INF로 세팅을 합니다.

변수에 대해  설명하자면 

res는 cost를 담는 정보이며,

visit은 탐색을 했는지 안했는지 정보를 담기 위한 변수이며 

prev 는 이후 Maximum flow 알고리즘을 위해 사용되는 변수입니다.

 

이후  Queue를 이용하여 노드탐색을 진행합니다. python에선 deque를 지원하여 deque를 사용하였습니다. 해당 그래프는 유량을 포함하는 그래프이므로 index number를 비교하여 해당 방향이 순방향인지 역방향인지를 비교해줍니다. 이 후 cost, 즉 노드와 노드 사이의 거리를 구해줍니다. 해당 거리를 바탕으로 현재 값의 cost와 인접 노드로 가는 cost를 더했을 때 인접노드의 cost 보다 작으면 인접노드의 cost값을 변경하며  현재 노드의 정보를 prev변수를 이용하여 인접 노드에 저장해줍니다. 이후 인접 노드들을 첫 방문했다면 이를  deque에 다시 추가하여 모든 노드들을 탐색하도록 진행 해줍니다. 

MCMF  Algorithm

    flow = float('inf') #flow를 무한대로 설정  , Natwork Flow alglorithm
    nxt = m + n + 1 #nxt를  m+n+1 로 설정 마지막 사람.
    while nxt: #nxt가 0이 되기전까지 반목
        cur = prev[nxt] #prev[nxt]를 가져옴 이게 cur 변수 , 즉 특정 사람 인덱스
        for i in range(len(graph[cur])): #그래프의 cur인덱스 길이 만큼 반복문 실행
            if graph[cur][i][0] == nxt: #그래프의 cur 인덱스의
                flow = min(flow, graph[cur][i][1])
                break
        nxt = cur

    nxt = m + n + 1 # 사람 마지막 노드 번호
    while nxt:
        cur = prev[nxt] # 사람 마지막 노드번호에 인접한 노드를 가져옴

        if 0 < cur < nxt < m + n + 1: # 인접한 노드가 현재 번호 보다 작으면 양의 간선이므로 weight , 즉 가중치를 더함.
            weight += flow * board[cur - 1][nxt - m - 1]   # board = 배송비 , flow = 보내야 하는 노드
        elif 0 < nxt < cur < m + n + 1: # 인접한 노드가 현재 번호 보다 크면 반대 방향이라는 의미이므로 가중치를 뺌.
            weight -= flow * board[nxt - 1][cur - m - 1]

        for i in range(len(graph[cur])): # 인접 노드의 graph 즉, 인접 노드에서 몇개의 인접 노드가 있는지 반복문을 돔.
            if graph[cur][i][0] == nxt: # 인접 노드에 초기 탐색 한 노드가 있다면
                graph[cur][i][1] -= flow # 인접 노드에 음의 flow를 흘려보냄.
                if graph[cur][i][1] == 0: # 만약 인접 노드의 flow가 0이라면
                    graph[cur].remove([nxt, 0]) # 해당 인접 노드를 지움.  아마 자기 자신을 향한 그래프라 생각해서 그런거 같음.
                break

        for i in range(len(graph[nxt])): # graph의 현재 인접 개수 만큼 반복함
            if graph[nxt][i][0] == cur: # 현재 노드에서 인접한 노드가 있다면
                graph[nxt][i][1] += flow # 양의 flow를 흘려 보냄
                break
        else:
            graph[nxt].append([cur, flow]) # 인접 개수가 없다면 현재 그래프에 인접노드와 flow를 추가함.

 

해당 알고리즘은 MCMF 알고리즘을 토대로 진행합니다. 기존 MCMF 와 약간의 다른점은 최대 유량을 구하므로 결과값은 경로 비용의 합 * 유량을 더해주면 됩니다.  해당 코드 review를 마치겠습니다.

 

생각보다 알고리즘 자체를 이해하는데에 있어 상당히 어려움을 겪었습니다. SPFA 알고리즘조차 모르던 상황이라 SPFA 알고리즘도 따로 공부하며 MCMF 알고리즘도 같이 이해를 하다보니 얄팍한 지식이 상당히 꼬여서 개념 자체를 잡는데 애를 먹었던 기억이 있었습니다..

해당 코드에 대하여 제가 공부한대로 review하고 분석한 것이라 해당 내용이 완벽하진 않을 수 있습니다.

이를 참고하여 봐주시면 감사하겠습니다.

 

참고: https://koosaga.com/18,     https://www.crocus.co.kr/1090

https://cael0.github.io/problem%20solving/BOJ11405/