[고급 알고리즘] 최대 유량 알고리즘

최대 유량 알고리즘(Max Flow Algorithm)

최대 유량 알고리즘은 그래프 내에서 특정 출발점에서 도착점까지의 최대 흐름을 찾는 문제를 해결하는 알고리즘입니다. 이 문제는 1950년대 Ford와 Fulkerson의 연구를 통해 처음 소개되었으며, 그 이후 다양한 연구와 알고리즘이 제안되었습니다.

1. Orlin의 연구

2013년, Orlin은 최대 유량 문제를 O(nm) 시간 안에 해결할 수 있다는 것을 증명했습니다. 그의 알고리즘은 O(nm + m^1.94) 시간 안에 실행되며, 이는 n^1.06 보다 적은 간선을 가진 그래프에 대해서는 가장 빠른 시간이었습니다. 그래프가 충분히 희소하지 않은 경우, King, Rao, Tarjan에 의한 알고리즘이 가장 빠른 실행 시간을 보였습니다.

2. 알고리즘의 특징

• 시간 복잡도: Orlin의 알고리즘은 O(nm + m^1.94)의 시간 복잡도를 가집니다. 이는 특히 m < n^1.06인 경우 O(nm)이 됩니다.
• 스케일링 알고리즘: 새로운 변형된 초과 스케일링 알고리즘을 사용하여, 그 실행 시간은 King 등의 알고리즘의 실행 시간을 엄격하게 지배합니다.

3. 예시

def max_flow(graph, source, sink):
    flow = 0
    while True:
        # BFS를 사용하여 경로 찾기
        path, path_flow = find_path(graph, source, sink)
        if not path:
            break
        flow += path_flow
        # 경로에 따라 그래프 업데이트
        for i in range(len(path) - 1):
            u, v = path[i], path[i+1]
            graph[u][v] -= path_flow
            graph[v][u] += path_flow
    return flow

4. 시간 복잡도

Orlin의 알고리즘의 시간 복잡도는 O(nm + m^1.94)입니다. 이는 그래프의 노드 수와 간선 수에 따라 달라집니다.