Minimum Cost Maximum Flow

주어진 유량을 보낼 때 발생하는 총 비용을 최소화 하는 경로를 찾는 알고리즘

1 그래프 구성 요소

• edge
  • capacity: 최대 유량
  • flow: 현재 유량
  • cost: 유량 1당 비용

메커니즘

1. 최단 경로 찾기 e.g. SPFA
   • source에서 sink까지 가는 경로중 비용의 합이 최소인 경로를 찾음
     • 잔여 용량이 존재하는 즉 (capacity > flow) 경로만 가능
2. 유량 업데이트
   • 찾은 최단 경로로 보낼 수 있는 최대 유량을 보냄
3. 역방향 간선 업데이트
   • 유량을 보낼 때, 반대 방향으로 가는 가상 간성을 만들어 비용을 음수로 설정
     • 유량 취소 선택지