[파이썬] 그래프 알고리즘을 활용한 네트워크 플로우

04 Sep 2023

python

네트워크 플로우(Network Flow)는 그래프 알고리즘 중 하나로, 노드와 간선으로 구성된 그래프에서 시작점과 도착점 사이의 최대 유량(Maximum Flow)을 구하는 문제입니다. 네트워크 플로우는 다양한 실제 문제에서 활용되며, 예를 들어 통신 네트워크의 최대 전송 용량, 배관 네트워크의 최대 유출량 등을 계산할 때 사용됩니다.

그래프 알고리즘 - Ford-Fulkerson 알고리즘

Ford-Fulkerson 알고리즘은 네트워크 플로우 문제를 해결하기 위한 가장 기본적인 그래프 알고리즘입니다. 이 알고리즘은 잔여 유량(Residual Flow) 그래프를 사용하여 최대 유량을 구합니다.

알고리즘의 기본 아이디어는 다음과 같습니다:

초기 유량을 0으로 설정하고, 잔여 유량 그래프를 생성합니다.
잔여 유량 그래프에서 증가 경로를 찾습니다. 증가 경로란, 시작점에서 도착점까지 연결된 간선들로 이루어진 경로 중에서 유량을 증가시킬 수 있는 경로입니다.
증가 경로를 찾으면, 해당 경로에서 최소 잔여 용량을 구하고 이를 증가 유량으로 할당합니다.
2~3단계를 반복하여 더 이상 증가 경로가 없을 때까지 반복합니다.

Python을 활용한 Ford-Fulkerson 구현

아래는 Python으로 Ford-Fulkerson 알고리즘을 구현한 예시 코드입니다:

class Graph:
    def __init__(self, graph):
        self.graph = graph
        self.ROW = len(graph)

    def bfs(self, s, t, parent):
        visited = [False] * (self.ROW)
        queue = []
        queue.append(s)
        visited[s] = True

        while queue:
            u = queue.pop(0)
            for ind, val in enumerate(self.graph[u]):
                if visited[ind] == False and val > 0:
                    queue.append(ind)
                    visited[ind] = True
                    parent[ind] = u

        return True if visited[t] else False

    def ford_fulkerson(self, source, sink):
        parent = [-1] * (self.ROW)
        max_flow = 0

        while self.bfs(source, sink, parent):
            path_flow = float("Inf")
            s = sink
            while s != source:
                path_flow = min(path_flow, self.graph[parent[s]][s])
                s = parent[s]

            max_flow += path_flow

            v = sink
            while v != source:
                u = parent[v]
                self.graph[u][v] -= path_flow
                self.graph[v][u] += path_flow
                v = parent[v]

        return max_flow


# 예시 그래프
graph = [[0, 16, 13, 0, 0, 0],
         [0, 0, 10, 12, 0, 0],
         [0, 4, 0, 0, 14, 0],
         [0, 0, 9, 0, 0, 20],
         [0, 0, 0, 7, 0, 4],
         [0, 0, 0, 0, 0, 0]]

g = Graph(graph)

source = 0  # 시작점
sink = 5   # 도착점

max_flow = g.ford_fulkerson(source, sink)
print("최대 유량:", max_flow)

위 예시 코드에서는 인접 행렬을 사용하여 그래프를 표현합니다. 시작점과 도착점을 설정하고 ford_fulkerson 메서드를 호출하여 최대 유량을 구할 수 있습니다.

네트워크 플로우 알고리즘은 여러 다양한 응용 분야에서 활용되며, 실제로도 다양한 알고리즘이 개발되어 있습니다. 그러나 Ford-Fulkerson 알고리즘은 네트워크 플로우 알고리즘의 기본 개념을 이해하는 데 도움이 됩니다.