최소 비용 흐름 - 연속 최단 경로 알고리즘¶
$n$개의 정점과 $m$개의 간선으로 이루어진 네트워크 $G$가 주어집니다. 각 간선(일반적으로 방향 간선이지만, 아래를 참고하십시오)마다 용량(음이 아닌 정수)과 해당 간선을 따라 흐르는 흐름 한 단위당 비용(임의의 정수)이 주어집니다. 또한 소스 $s$와 싱크 $t$가 지정되어 있습니다.
주어진 값 $K$에 대해 그만큼의 양을 갖는 흐름을 찾아야 하며, 그러한 양의 모든 흐름 중에서 비용이 가장 낮은 흐름을 골라야 합니다. 이 문제를 최소 비용 흐름 문제라고 합니다.
때로는 문제가 조금 다르게 주어지기도 합니다. 최대 흐름을 찾되, 모든 최대 흐름 중에서 비용이 가장 적은 것을 찾고자 하는 경우입니다. 이를 최소 비용 최대 흐름 문제라고 합니다.
이 두 문제는 모두 연속 최단 경로 알고리즘으로 효과적으로 풀 수 있습니다.
알고리즘¶
이 알고리즘은 최대 흐름을 계산하는 Edmonds-Karp와 매우 비슷합니다.
가장 단순한 경우¶
먼저 그래프가 방향 그래프이고, 임의의 정점 쌍 사이에 간선이 최대 하나만 있는 가장 단순한 경우만 고려합니다(예를 들어 $(i, j)$가 그래프의 간선이라면 $(j, i)$는 그래프에 함께 속할 수 없습니다).
간선 $(i, j)$가 존재할 때, $U_{i j}$를 그 간선의 용량이라고 합시다. 그리고 $C_{i j}$를 이 간선 $(i, j)$를 따라 흐르는 흐름 한 단위당 비용이라고 합시다. 마지막으로 $F_{i, j}$를 간선 $(i, j)$를 따라 흐르는 흐름이라고 합시다. 처음에는 모든 흐름 값이 0입니다.
네트워크를 다음과 같이 수정합니다. 각 간선 $(i, j)$마다 용량이 $U_{j i} = 0$이고 비용이 $C_{j i} = -C_{i j}$인 역방향 간선 $(j, i)$를 네트워크에 추가합니다. 앞서 둔 제약에 따르면 간선 $(j, i)$는 원래 네트워크에 없었으므로, 이렇게 바꾼 네트워크도 여전히 멀티그래프(다중 간선이 있는 그래프)가 아닙니다. 또한 알고리즘을 진행하는 동안 조건 $F_{j i} = -F_{i j}$가 항상 참이 되도록 유지합니다.
어떤 고정된 흐름 $F$에 대한 잔여 네트워크를 다음과 같이 정의합니다(Ford-Fulkerson 알고리즘에서와 똑같습니다). 잔여 네트워크는 포화되지 않은 간선(즉, $F_{i j} < U_{i j}$인 간선)만 포함하며, 그러한 각 간선의 잔여 용량은 $R_{i j} = U_{i j} - F_{i j}$입니다.
이제 최소 비용 흐름을 계산하는 알고리즘에 대해 이야기할 수 있습니다. 알고리즘의 각 반복에서는 잔여 그래프에서 $s$로부터 $t$까지의 최단 경로를 찾습니다. Edmonds-Karp와 달리, 간선의 개수 대신 경로의 비용을 기준으로 최단 경로를 찾습니다. 그러한 경로가 더 이상 존재하지 않으면 알고리즘이 종료됩니다. 현재 흐름이 아직 $K$에 도달하지 못했다면 값이 $K$인 흐름은 존재하지 않습니다. 그렇지 않다면 $F$가 구하려는 흐름입니다. 경로를 찾았다면 그 경로를 따라 흐름을 가능한 한 많이 늘립니다(즉, 경로의 최소 잔여 용량 $R$을 찾아 그만큼 흐름을 늘리고, 역방향 간선은 같은 양만큼 줄입니다). 어느 시점에 흐름이 값 $K$에 도달하면 알고리즘을 멈춥니다(알고리즘의 마지막 반복에서는 최종 흐름 값이 $K$를 넘지 않을 만큼만 흐름을 늘려야 한다는 점에 유의하십시오).
$K$를 무한대로 두면 이 알고리즘이 최소 비용 최대 흐름을 찾는다는 것은 어렵지 않게 알 수 있습니다. 따라서 두 가지 변형 문제 모두 같은 알고리즘으로 풀 수 있습니다.
무방향 그래프 / 멀티그래프¶
무방향 그래프나 멀티그래프의 경우도 개념적으로는 위의 알고리즘과 다르지 않습니다. 이 알고리즘은 이러한 그래프에서도 동작합니다. 다만 구현하기가 조금 더 까다로워집니다.
무방향 간선 $(i, j)$는 사실 용량과 비용이 같은 두 방향 간선 $(i, j)$와 $(j, i)$와 같습니다. 위에서 설명한 최소 비용 흐름 알고리즘은 각 방향 간선마다 역방향 간선을 만들기 때문에 무방향 간선 하나가 방향 간선 $4$개로 나뉘며, 결과적으로 실제로는 멀티그래프를 얻게 됩니다.
다중 간선은 어떻게 처리해야 합니까? 첫째, 다중 간선 각각의 흐름을 따로 저장해야 합니다. 둘째, 최단 경로를 탐색할 때 다중 간선 중 어느 간선이 경로에 사용되는지가 중요하다는 점을 고려해야 합니다. 따라서 일반적인 조상 배열 대신, 조상과 함께 그 조상에서 어느 간선 번호를 따라 왔는지도 저장해야 합니다. 셋째, 어떤 간선을 따라 흐름이 증가하면 역방향 간선을 따라 흐름을 감소시켜야 합니다. 다중 간선이 있으므로 각 간선마다 역방향 간선의 번호를 저장해야 합니다.
무방향 그래프나 멀티그래프에서는 이 밖에 다른 어려움은 없습니다.
복잡도¶
이 알고리즘은 일반적으로 입력 크기에 대해 지수 시간이 걸립니다. 좀 더 구체적으로 말하면, 최악의 경우 각 반복마다 흐름을 겨우 $1$단위만 보낼 수 있으므로 크기가 $F$인 최소 비용 흐름을 찾는 데 $O(F)$번의 반복이 필요하며, 전체 실행 시간은 $O(F \cdot T)$가 됩니다. 여기서 $T$는 소스에서 싱크까지의 최단 경로를 찾는 데 필요한 시간입니다.
이를 위해 Bellman-Ford 알고리즘을 사용하면 실행 시간은 $O(F mn)$이 됩니다. 또한 Dijkstra 알고리즘을 수정하여 초기 단계로 $O(nm)$의 전처리를 수행한 뒤 각 반복을 $O(m \log n)$에 처리하도록 만들 수도 있으며, 이 경우 전체 실행 시간은 $O(mn + F m \log n)$이 됩니다. 여기에 이러한 알고리즘이 $O(2^{n/2} n^2 \log n)$ 시간을 필요로 하는 그래프의 생성기가 있습니다.
수정된 Dijkstra 알고리즘은 Johnson 알고리즘의 이른바 포텐셜을 사용합니다. 이 알고리즘과 Dinic 알고리즘의 아이디어를 결합하면 반복 횟수를 $F$에서 $\min(F, nC)$로 줄일 수 있습니다. 여기서 $C$는 간선들 중 최대 비용입니다. 포텐셜과 이를 Dinic 알고리즘과 결합하는 방법에 대해서는 여기에서 더 읽어 보실 수 있습니다.
구현¶
다음은 가장 단순한 경우에 대해 SPFA 알고리즘을 사용한 구현입니다.
struct Edge
{
int from, to, capacity, cost;
};
vector<vector<int>> adj, cost, capacity;
const int INF = 1e9;
void shortest_paths(int n, int v0, vector<int>& d, vector<int>& p) {
d.assign(n, INF);
d[v0] = 0;
vector<bool> inq(n, false);
queue<int> q;
q.push(v0);
p.assign(n, -1);
while (!q.empty()) {
int u = q.front();
q.pop();
inq[u] = false;
for (int v : adj[u]) {
if (capacity[u][v] > 0 && d[v] > d[u] + cost[u][v]) {
d[v] = d[u] + cost[u][v];
p[v] = u;
if (!inq[v]) {
inq[v] = true;
q.push(v);
}
}
}
}
}
int min_cost_flow(int N, vector<Edge> edges, int K, int s, int t) {
adj.assign(N, vector<int>());
cost.assign(N, vector<int>(N, 0));
capacity.assign(N, vector<int>(N, 0));
for (Edge e : edges) {
adj[e.from].push_back(e.to);
adj[e.to].push_back(e.from);
cost[e.from][e.to] = e.cost;
cost[e.to][e.from] = -e.cost;
capacity[e.from][e.to] = e.capacity;
}
int flow = 0;
int cost = 0;
vector<int> d, p;
while (flow < K) {
shortest_paths(N, s, d, p);
if (d[t] == INF)
break;
// find max flow on that path
int f = K - flow;
int cur = t;
while (cur != s) {
f = min(f, capacity[p[cur]][cur]);
cur = p[cur];
}
// apply flow
flow += f;
cost += f * d[t];
cur = t;
while (cur != s) {
capacity[p[cur]][cur] -= f;
capacity[cur][p[cur]] += f;
cur = p[cur];
}
}
if (flow < K)
return -1;
else
return cost;
}