포드 풀커슨
-
[Algorithm] 네트워크 플로우 (Network Flow)Problem Solving/Algorithm 2020. 3. 9. 00:59
네트워크 플로우 (Network Flow) 란? - 각 노드의 용량이 정해진 상태에서, 시작점에서 끝점까지 흐르는 최대 유량을 구하는 알고리즘 - 네트워크 데이터 전송, 교통 체증, 물류 시스템 등에 활용 [용어] - S : 시작점 (Source) - T : 도착점 (Sink) - c(a, b) : a에서 b로 흐를 수 있는 최대 양 (Capacity) - f(a, b) : a에서 b로 흐른 실제 양 (Flow) [제약 조건] - 용량 제한 속성 : f(u, v)