---
# System prepended metadata

title: 디니츠 알고르즘

---

# 디니츠 알고르즘
- 일시: 2021년 11월 9일(월) 20:00


- 디니츠 알고리즘 유래
- 최대유량 문제
- 시간복잡도, 공간복잡도
- 알고르즘 원리
    - ① 레벨 그래프를 만든다. 이때 싱크에 도달할 수 없다면 종료한다.
    - ② 레벨 그래프에서 차단 유량을 찾아 그만큼을 총 유량에 더하고, ①로 돌아간다. 
- 예시
- 유량의 음수 = 유량의 대칭성

- 참고자료
    - https://m.blog.naver.com/kks227/220812858041
    - https://slideplayer.com/slide/4833125/
    - https://www.geeksforgeeks.org/dinics-algorithm-maximum-flow/
    - https://everenew.tistory.com/177