그래프에서 음수 사이클 찾기¶
정점 $N$개와 간선 $M$개로 이루어진 방향 가중치 그래프 $G$가 주어집니다. 그래프에 음수 가중치 사이클이 존재한다면 그러한 사이클을 아무것이나 하나 찾으십시오.
이 문제의 또 다른 형태에서는 두 정점 사이에 임의로 작은 가중치의 경로가 존재하는 정점 쌍을 모두 찾아야 합니다.
이 두 가지 변형 문제는 서로 다른 알고리즘으로 푸는 것이 편리하므로, 여기서는 두 가지를 모두 다루겠습니다.
Bellman-Ford 알고리즘 사용하기¶
Bellman-Ford 알고리즘을 사용하면 그래프에 음수 가중치 사이클이 존재하는지 확인할 수 있고, 존재한다면 그러한 사이클 중 하나를 찾을 수 있습니다.
알고리즘의 자세한 내용은 Bellman-Ford 알고리즘 문서에 설명되어 있습니다. 여기서는 이 문제에 대한 응용만 설명하겠습니다.
Bellman-Ford의 표준 구현은 어떤 시작 정점 $v$에서 도달할 수 있는 음수 사이클을 찾지만, 알고리즘을 수정하여 그래프의 임의의 음수 사이클을 찾도록 할 수 있습니다. 이를 위해서는 모든 거리 $d[i]$를 무한대가 아닌 0으로 설정해야 합니다. 이는 마치 모든 정점에서 동시에 최단 경로를 찾는 것과 같으며, 음수 사이클 검출의 타당성에는 영향을 주지 않습니다.
Bellman-Ford 알고리즘을 $N$번 반복합니다. 마지막 반복에서 변화가 없었다면 그래프에는 음수 가중치 사이클이 없습니다. 그렇지 않다면 거리가 변경된 정점 하나를 골라, 사이클이 발견될 때까지 그 정점에서부터 조상을 따라 거슬러 올라갑니다. 이 사이클이 바로 찾고자 하는 음수 가중치 사이클입니다.
구현¶
struct Edge {
int a, b, cost;
};
int n;
vector<Edge> edges;
const int INF = 1000000000;
void solve() {
vector<int> d(n, 0);
vector<int> p(n, -1);
int x;
for (int i = 0; i < n; ++i) {
x = -1;
for (Edge e : edges) {
if (d[e.a] + e.cost < d[e.b]) {
d[e.b] = max(-INF, d[e.a] + e.cost);
p[e.b] = e.a;
x = e.b;
}
}
}
if (x == -1) {
cout << "No negative cycle found.";
} else {
for (int i = 0; i < n; ++i)
x = p[x];
vector<int> cycle;
for (int v = x;; v = p[v]) {
cycle.push_back(v);
if (v == x && cycle.size() > 1)
break;
}
reverse(cycle.begin(), cycle.end());
cout << "Negative cycle: ";
for (int v : cycle)
cout << v << ' ';
cout << endl;
}
}
Floyd-Warshall 알고리즘 사용하기¶
Floyd-Warshall 알고리즘을 사용하면 두 번째 변형 문제, 즉 사이에 최단 경로가 존재하지 않는(즉, 임의로 작은 가중치의 경로가 존재하는) 정점 쌍 $(i, j)$를 모두 찾는 문제를 풀 수 있습니다.
이번에도 자세한 내용은 Floyd-Warshall 문서에서 찾을 수 있으며, 여기서는 그 응용만 설명합니다.
그래프에 Floyd-Warshall 알고리즘을 실행합니다. 처음에는 각 $v$에 대해 $d[v][v] = 0$입니다. 그러나 알고리즘을 실행한 후, $v$에서 $v$로 가는 음수 길이의 경로가 존재한다면 $d[v][v]$는 $0$보다 작아집니다. 이를 이용하면 사이에 최단 경로가 존재하지 않는 정점 쌍도 모두 찾을 수 있습니다. 모든 정점 쌍 $(i, j)$를 순회하면서 각 쌍 사이에 최단 경로가 존재하는지 확인합니다. 이를 위해 중간 정점 $t$로 가능한 모든 경우를 시도합니다. 중간 정점 $t$ 중 하나가 $d[t][t] < 0$을 만족하고(즉, $t$가 음수 가중치 사이클의 일부이고), $i$에서 $t$에 도달할 수 있으며 $t$에서 $j$에 도달할 수 있다면, $(i, j)$에는 최단 경로가 존재하지 않습니다. 이 경우 $i$에서 $j$로 가는 경로는 임의로 작은 가중치를 가질 수 있습니다. 이를 -INF로 표시하겠습니다.
구현¶
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
for (int t = 0; t < n; ++t) {
if (d[i][t] < INF && d[t][t] < 0 && d[t][j] < INF)
d[i][j] = - INF;
}
}
}