디닉 알고리즘
디닉 알고리즘은 레벨 그래프와 차단 흐름을 사용해 유량을 여러 번 묶어 증가시키는 알고리즘이다 그래프 알고리즘의 최대 유량 분야에 속한다. 그래프의 정점·간선에 대한 관계를 계산하며, 간선의 방향·가중치와 허용하는 입력 구조에 따라 결과의 의미가 달라진다. 이 알고리즘의 전제는 잔여 용...
| 분류 | 알고리즘 · 그래프 알고리즘 · 최대 유량 |
|---|---|
| 문제 | 레벨 그래프와 차단 흐름을 사용해 유량을 여러 번 묶어 증가시키는 알고리즘이다 |
| 입력 | 잔여 용량·역방향 간선과 레벨 그래프의 조건이 정확해야 한다 |
| 핵심 단계 | BFS로 잔여 네트워크의 레벨을 계산하고, DFS로 레벨이 증가하는 간선만 따라 차단 흐름을 만든다 |
| 시간 복잡도 | O(V²E) |
| 공간·구현 | 일반 용량 네트워크에서 O(V²E); 단위 용량에서는 더 나은 상한이 있다 |
| 관련 분야 | 그래프, 자료구조 |
| 참고 문헌 | MIT Algorithms |
디닉 알고리즘은 레벨 그래프와 차단 흐름을 사용해 유량을 여러 번 묶어 증가시키는 알고리즘이다 그래프 알고리즘의 최대 유량 분야에 속한다. 그래프의 정점·간선에 대한 관계를 계산하며, 간선의 방향·가중치와 허용하는 입력 구조에 따라 결과의 의미가 달라진다. 이 알고리즘의 전제는 잔여 용량·역방향 간선과 레벨 그래프의 조건이 정확해야 한다.[1]
핵심 절차는 BFS로 잔여 네트워크의 레벨을 계산하고, DFS로 레벨이 증가하는 간선만 따라 차단 흐름을 만든다. 레벨을 다시 구성하며 더 이상 증가 경로가 없을 때 종료한다. 구현에서는 각 정점 또는 간선에 기록된 상태가 어떤 의미를 갖는지 불변식을 정의하고, 탐색·갱신 과정에서 해당 상태를 일관되게 유지해야 한다.
계산 비용은 일반 용량 네트워크에서 O(V²E); 단위 용량에서는 더 나은 상한이 있다 정점 수를 V, 간선 수를 E라고 나타낼 때 O(V²E)의 시간 특성을 가진다. 저장 공간은 그래프의 표현 방식, 큐·스택·우선순위 큐 및 결과 배열의 선택에 영향을 받으므로 실제 적용 시 구현 구조를 함께 분석한다.
최대 유량·이분 매칭 등에서 자주 사용한다. 단순 DFS 증가 경로보다 실용적으로 빠른 경우가 많다. 대표적인 변형 알고리즘 및 자료구조의 선택은 결과의 최적성, 음수 가중치나 사이클의 허용 여부, 희소·밀집 그래프 여부에 따라 달라진다. 동점 처리와 비연결 그래프 등의 경계 사례까지 정의해야 구현 결과가 명확해진다.[2]