최소 비용 최대 유량 계산기

간선마다 단위 비용이 하나 더 붙는다는 점이 다릅니다. 최대 유량은 「얼마나 흘릴 수 있나」만 보지만, 여기서는 같은 양을 흘리는 여러 방법 중 비용이 가장 적은 것을 찾습니다. 흘리는 양은 두 계산이 같고 비용만 달라집니다.

잔여 그래프에서 비용이 가장 싼 길을 찾아 흘릴 수 있는 만큼 흘리기를 되풀이하는 방법입니다. 최대 유량이 간선 수가 가장 적은 길을 고르는 것과 달리 여기서는 비용이 가장 싼 길을 고릅니다. 매번 가장 싼 길로만 늘리면 각 단계의 유량이 그 유량값에서 비용 최소가 된다는 정리가 근거입니다.

잔여 그래프에 음수 비용 간선이 반드시 생기기 때문입니다. u→v로 c원짜리를 흘리면 되무르기용 v→u 간선이 만들어지는데, 무르면 냈던 비용을 돌려받으므로 그 간선의 비용은 −c입니다. 다익스트라는 음수 간선에서 틀린 답을 내므로 벨만–포드를 쓰거나 존슨 퍼텐셜로 비용을 비음수로 바꿔야 합니다. 이 계산기는 벨만–포드를 씁니다.

싼 길이 먼저 꽉 차고 남은 길이 비싸지기 때문입니다. 매 단계에서 잔여 그래프의 최단 비용은 이전 단계보다 작아질 수 없고, 이 성질이 SSP가 최적을 낸다는 증명의 뼈대이기도 합니다. 표에서 단위비용 열이 내려가지 않는 것으로 확인할 수 있습니다.

풀 수 있습니다. 공장마다 공급량을 용량으로 준 간선을 가상의 출발점에서 잇고, 창고마다 수요량을 용량으로 준 간선을 가상의 도착점으로 이으면 그대로 최소 비용 유량 문제가 됩니다. 사람을 일에 배정하는 배정 문제도 용량을 모두 1로 둔 같은 틀입니다. 예시의 「수송 문제」를 눌러 보세요.

넣을 수 없습니다. 원래 간선에 음수 비용이 있으면 잔여 그래프에 음수 순환이 생겨 SSP의 전제가 깨지기 때문입니다. 이 계산기는 단위비용을 0 이상만 받습니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.