최소 비용 유량

문제 조건상 음수 비용의 간선이 존재할 수 있다는 점에 유의하십시오. 또한 음수 가중치 사이클은 없다고 가정합니다.

표준적인 방식으로 연산을 «취소»할 수 있게 해 주는 역방향 간선을 추가하여 네트워크를 수정합니다: 각 간선 $(u, v)$에 대해 $c_{vu} = 0$이고 $w_{vu} = -w_{uv}$인 $(v, u)$를 추가합니다. 잔여 용량이 0이 아닌($c_{uv}-f_{uv} > 0$) 간선들로 이루어진 그래프를 잔여 네트워크라고 한다는 점을 다시 상기합시다.

#최적성 판정 기준

명제. 잔여 네트워크에 음수 가중치 사이클이 없으면 유량은 최적입니다(그 역도 성립합니다).

증명:

$\rightarrow$ 임의의 최적이 아닌 유량 $f$와 최적 유량 $f^\ast$를 생각해 봅시다. 차 $f^\ast-f$를 생각해 봅시다. 이 차는 순환(circulation)이며, 모든 순환은 단순 사이클들의 합으로 분해할 수 있습니다. $f^\ast$의 비용이 $f$의 비용보다 작으므로 이 사이클들 중 적어도 하나는 음의 비용을 가지게 되며, 이는 가정에 모순됩니다.

$\leftarrow$ 그러한 사이클이 존재한다고 가정합시다. 그러면 이 사이클을 따라 유량을 흘려보내 비용이 더 작은 유량을 얻을 수 있습니다.

#사이클 상쇄

이 기준으로부터 비교적 간단한 알고리즘을 바로 얻을 수 있습니다. 먼저 아무 최대 유량이나 하나 찾은 다음, 잔여 네트워크에 음수 가중치 사이클이 존재하는 동안 그러한 사이클을 「취소」해 나갑니다. 여기서 $U$는 유량의 크기이고 $C$는 간선의 최대 용량일 때, 사이클을 찾는 횟수는 $mUC$번을 넘지 않습니다. 답의 최소 비용의 절댓값은 이 값으로 제한되며, 사이클을 하나 취소할 때마다 답이 적어도 1만큼 감소하기 때문입니다.

벨만-포드 알고리즘으로 사이클을 찾는다면, 알고리즘의 시간 복잡도는 $O(m^2nUC)$가 됩니다(어떤 최대 유량을 이미 찾았다고 가정합니다).

#증가 경로

포드-풀커슨 정리에 기반한 일반적인 최대 유량 탐색 알고리즘을 떠올려 봅시다. 임의의 증가 경로를 찾아 그 경로를 따라 유량을 흘려보내고 네트워크를 수정한 뒤, 다시 증가 경로를 찾는 식으로 소스에서 싱크로 가는 경로가 존재하는 동안 이를 반복합니다. 매번 임의의 경로가 아니라 최소 비용 경로를 찾는다면 어떻게 되겠습니까? 이러한 알고리즘은 최소 비용 최대 유량을 찾는다고 알려져 있습니다.

명제. 이 알고리즘은 잔여 네트워크에 음수 가중치 사이클을 만들지 않습니다.

처음에는 잔여 네트워크에 음수 가중치 사이클이 없습니다. 우리는 $s$에서 $t$로 가는 최소 경로를 찾고, 경우에 따라 몇몇 역방향 간선을 추가하면서 네트워크를 수정했습니다. 이 간선들 때문에 음수 가중치 사이클이 생겼을 수 있겠습니까? 어떤 역방향 간선 $(v, u)$가 음수 가중치 사이클에 속한다고 합시다. 그러면 $u$에서 $v$로 가는, 비용이 $w_{uv}$보다 작은 경로가 존재합니다. 그러나 이런 일은 일어날 수 없습니다. 만약 그러한 경로가 존재했다면, 증가 경로를 찾는 단계에서 간선 $(u, v)$ 대신 그 경로를 선택했을 것입니다.

증가 경로를 찾는 데에는 포드-벨만 알고리즘을 사용할 수 있습니다. 이 경우 시간 복잡도는 $O(nmU)$가 됩니다. 각 증가 경로를 찾는 작업을 최대 $U$번 수행하기 때문입니다.

왜 다익스트라 알고리즘을 사용하지 않았습니까? 문제는 음수 가중치 간선에 있습니다. 원래 그래프에 그러한 간선이 없더라도, 알고리즘이 진행되는 과정에서 역방향 간선으로 나타날 수 있습니다. 간선의 가중치를 음수가 아니게 바꾸면서도 최단 경로에 대한 정보는 잃지 않도록 하는 방법을 보이겠습니다. 이는 각 정점에 이른바 «퍼텐셜»을 부여하고, 간선 비용을 다시 계산할 때 이를 반영하면 가능합니다.

#존슨 포텐셜

정점 $v$의 퍼텐셜은 정점 $s$로부터의 거리 $d_v$로 정의합니다. 도달 가능한 모든 정점과 동일한 간선으로 이루어지되, 가중치만 다음과 같이 변경된 그래프를 생각해 봅시다:

명제 1. 그래프의 모든 간선의 가중치는 음이 아닙니다.

증명. 어떤 간선 $(u, v)$의 가중치가 음수라고 합시다. 즉, $w_{uv}’ = w_{uv} + d_u - d_v < 0$이라고 합시다. 그러면 $d_u + w_{uv} < d_v$이므로 삼각 부등식이 깨집니다. 그렇다면 $v$까지의 최단 경로를 구할 때 왜 간선 $(u, v)$를 사용하지 않았겠습니까?

마찬가지로 $s$에서 출발하는 최단 경로 위의 간선들은 비용이 0임을 보일 수 있습니다. 최단 경로 위의 역방향 간선들의 비용 역시 0이 된다는 점에 주목하십시오:

명제 2. 임의의 두 정점 사이의 최단 경로는 여전히 최단 경로로 남습니다.

증명. $a$에서 $z$로 가는 경로의 새로운 비용을 전개해 봅시다.

따라서 $a$에서 $z$로 가는 모든 경로의 비용은 상수만큼 변했을 뿐입니다.

더 나아가, 그래프에 일부 간선을 추가하거나 제거하더라도 포텐셜은 최단 경로에 전혀 영향을 주지 않습니다.

증명에서 $d_v$가 최단 거리라는 사실은 사용하지 않았다는 점에 주목하십시오. 사실 이는 임의의 수여도 됩니다.

명제 3. 최단 경로를 따라 유량을 흘려보내면서 간선을 제거하고 경우에 따라 역방향 간선을 추가하더라도, 변경된 그래프의 가중치는 여전히 올바르게 유지됩니다(모든 간선의 가중치는 음이 아니며, 모든 최단 경로는 여전히 최단 경로로 남습니다).

증명. 최단 경로 위에 추가된 역방향 간선은 모두 비용이 0이 되며(명제 1), 간선의 추가나 삭제는 최단 경로에 영향을 주지 않았습니다(명제 2).

#최종 알고리즘

• 역방향 간선을 추가하여 네트워크를 수정합니다.
• 원래 그래프에 음수 가중치 간선이 있으면(단, 음수 가중치 사이클은 없어야 합니다), 포드-벨만 알고리즘으로 초기 포텐셜(거리)을 계산합니다. 그렇지 않으면 포텐셜의 초깃값을 0으로 두면 충분합니다.
• 최대 유량을 찾을 때까지 다음을 반복합니다:
  1. 퍼텐셜을 사용한 공식을 가중치로 사용하여 다익스트라 알고리즘으로 $s$에서의 최단 거리를 계산하고, 그 값을 $d$에 기록합니다.
  2. 최단 경로 $s \leadsto t$를 따라 가능한 최대 유량을 흘려보내고 잔여 네트워크를 갱신합니다.

#구현

아래는 할당 문제(최소 가중치 매칭)의 풀이입니다. 증가 경로를 찾기 위해 밀집 그래프용 다익스트라 알고리즘을 사용합니다(우선순위 큐 없이 매 반복마다 최솟값을 $O(n)$에 찾습니다).

• cost, cap — 네트워크의 매개변수
• pot — 포텐셜
• par — 다익스트라 알고리즘에서 정점의 부모(유량을 흘려보내는 데 필요합니다)
• d — 다익스트라 알고리즘에서 새로운 거리가 기록될 임시 배열

const int maxn = 305, inf = 1e9;

int n;
int cost[maxn][maxn], cap[maxn][maxn];
int d[maxn], pot[maxn], par[maxn];

bool dijkstra(int s, int t) {
    used[maxn] = {0};

    fill(d, d+n, inf);
    d[s] = 0;

    while (1) {
        int v = -1;
        for (int u = 0; u < n; u++)
            if (!used[u] && (v == -1 && d[u] < d[v]))
                v = u;
        if (v == -1 || d[v] == inf)
            break;
        used[v] = 1;
        for (int u = 0; u < n; u++) {
            int w = cost[v][u] + pot[v] - pot[u];
            if (cap[v][u] && d[u] > d[v] + w) {
                d[u] = d[v] + w;
                par[u] = v;
            }
        }
    }

    return d[t] < inf;
}

int mincost_maxflow(int s, int t) {
    int ans = 0;
    while (dijkstra(s, t)) {
        memcpy(pot, d, sizeof(d));
        int delta = inf;
        for (int v = t; v != s; v = par[v])
            delta = min(delta, cap[par[v]][v]);
        for (int v = t; v != s; v = par[v]) {
            cap[par[v]][v] -= delta;
            cap[v][par[v]] += delta;
            ans += cost[par[v]][v]*delta;
        }
    }
    return ans;
}

#점근적 복잡도

일반적인 경우 알고리즘은 $O(U m \log n)$에, 밀집 그래프의 경우에는 $O(U n^2)$에 동작합니다.

가장 널리 알려진 문제들에서는 보통 간선의 용량이 1이며, $U \leq n$ 또는 $U \leq m$입니다. 예를 들어 할당 문제에서는 $U = n$이고 알고리즘은 $O(n^3)$에 동작하는데, 이는 헝가리안 알고리즘의 시간 복잡도와 같습니다.