사용자 도구

사이트 도구


ps:최소_비용_최대_유량

최소 비용 최대 유량 (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
  • Johnson’s Algorithm
    • (=Cycle Canceling ?)
    • 그래프에서 최단 경로를 유지하면서 negative 엣지를 없애주는 알고리즘이다. 이 알고리즘을 사용해서 negative edge를 없애주면, 최단 경로를 다익스트라 알고리즘으로 O(ElogV) 또는 O(V^2) 에 구할수 있다
    • 그러면 MCMF의 총 시간복잡도가 O(fElogV) 이나 O(fV^2) 으로 단축되긴 한다.
  • Push relabeling (=Cost Scaling)
  • 최소 비용 이분 매칭
    • 헝가리안 알고리즘

토론

댓글을 입력하세요:
K I V T Z
 
ps/최소_비용_최대_유량.txt · 마지막으로 수정됨: 2022/06/23 02:56 저자 teferi