최소 비용 최대 유량 (MCMF, Minimum Cost Maximum Flow)

[작성중]

• Successive shortest path
  • (=capacity scaling ??)
  • 가장 널리 쓰이는 방법. 포드풀커슨 알고리즘과 비슷한 원리로, Shortest path를 찾고, 그 패스에 플로우를 할당하는 것을 반복한다
  • 음수 엣지가 존재하므로, 최단경로를 찾을때에는 벨만-포드나 SPFA를 써야 한다. 따라서 최단 경로를 한번 찾는 시간복잡도는 O(VE)
    • 벨만포드는 O(VE)지만, SPFA는 최악 O(VE), 평균 O(E)이다. 일반적인 최단경로 문제를 풀때에는 저격 데이터들도 많고 해서 SPFA도 그냥 O(VE)고 벨만포드와 큰 차이가 없다고 생각했지만 MCMF처럼 최단경로 계산을 반복적으로 해야하는 상황에서는 벨만포드보다 확실히 메리트가 있는듯 하다
  • O(f)만큼 최단경로 찾는것을 반복해야 하므로 최종 시간복잡도는 O(fVE)로 알려져있다.
    • https://cp-algorithms.com/graph/min_cost_flow.html 에서는 에드몬드-카프 알고리즘과 같은 형태이므로 O(VE)번만 최단경로를 찾으면 된다고 한다. 그러면 O(V^2E^2) 인데.. 국내 다른 자료에서는 이렇게 쓰여있는것을 본적이 없어서 확인이 좀 필요하다.
• zkw MCMF
  • Dinic 알고리즘과 비슷하게, level 그래프를 만들고 유량을 흘리는 방식이 가능하다고 한다.
  • https://justicehui.github.io/hard-algorithm/2020/03/24/effective-mcmf/ 참고
  • 시간복잡도 자체가 줄어드는거는 아닌거 같고, 그냥 약간의 커팅인듯.. sparse 그래프에서 빠르게 작동한다고 한다
• Johnson’s Algorithm
  • (=Cycle Canceling ?)
  • 그래프에서 최단 경로를 유지하면서 negative 엣지를 없애주는 알고리즘이다. 이 알고리즘을 사용해서 negative edge를 없애주면, 최단 경로를 다익스트라 알고리즘으로 O(ElogV) 또는 O(V^2) 에 구할수 있다
  • 그러면 MCMF의 총 시간복잡도가 O(fElogV) 이나 O(fV^2) 으로 단축되긴 한다.
• Push relabeling (=Cost Scaling)
  • https://koosaga.com/289
  • O(V^3log(VC))

• 최소 비용 이분 매칭
  • 헝가리안 알고리즘