Bellman-Ford 알고리즘¶
음수 가중치 간선이 있는 단일 출발점 최단 경로
정점 $n$개와 간선 $m$개로 이루어진 가중치 방향 그래프 $G$와 지정된 정점 $v$가 주어졌다고 가정합시다. 정점 $v$에서 다른 모든 정점까지의 최단 경로 길이를 구하려고 합니다.
Dijkstra 알고리즘과 달리, 이 알고리즘은 음수 가중치 간선을 포함하는 그래프에도 적용할 수 있습니다. 그러나 그래프에 음수 사이클이 있으면 일부 정점까지의 최단 경로가 존재하지 않을 수 있음은 분명합니다(최단 경로의 가중치가 음의 무한대가 되어야 하기 때문입니다). 하지만 이 알고리즘을 수정하면 음수 가중치 사이클이 있음을 알리거나 그 사이클을 찾아낼 수도 있습니다.
이 알고리즘의 이름은 두 미국 과학자 Richard Bellman과 Lester Ford에게서 따왔습니다. Ford는 실제로 1956년에 다른 수학 문제를 연구하던 중 이 알고리즘을 고안했습니다. 그 문제는 결국 그래프에서 최단 경로를 찾는 부분 문제로 귀결되었고, Ford는 이 문제를 해결하는 알고리즘의 개요를 제시했습니다. Bellman은 1958년에 최단 경로를 찾는 문제만을 다룬 논문을 발표했으며, 이 논문에서 오늘날 우리에게 알려진 형태로 알고리즘을 명확하게 정식화했습니다.
알고리즘 설명¶
그래프에 음수 가중치 사이클이 없다고 가정합시다. 음수 가중치 사이클이 있는 경우는 아래의 별도 절에서 다루겠습니다.
거리 배열 $d[0 \ldots n-1]$을 만들겠습니다. 알고리즘을 실행하고 나면 이 배열에 문제의 답이 담깁니다. 처음에는 $d[v] = 0$으로 두고, 나머지 원소 $d[ ]$는 모두 무한대 $\infty$로 채웁니다.
알고리즘은 여러 단계로 이루어집니다. 각 단계에서는 그래프의 모든 간선을 훑으며, 알고리즘은 가중치가 $c$인 각 간선 $(a,b)$를 따라 완화를 시도합니다. 간선을 따라 완화한다는 것은 $d[a] + c$ 값을 이용해 $d[b]$ 값을 개선하려고 시도하는 것입니다. 즉, 간선 $(a,b)$와 정점 $a$의 현재 답을 이용해 이 정점의 답을 개선하려는 것입니다.
알고리즘을 $n-1$단계만 수행해도 그래프의 모든 최단 경로 길이를 올바르게 계산할 수 있다고 알려져 있습니다(다시 말하지만, 음수 가중치 사이클은 없다고 가정합니다). 도달할 수 없는 정점의 거리 $d[ ]$는 무한대 $\infty$로 남습니다.
구현¶
다른 여러 그래프 알고리즘과 달리 Bellman-Ford 알고리즘에서는 그래프를 모든 간선을 담은 하나의 리스트로 표현하는 편이 더 편리합니다($n$개의 간선 리스트, 즉 정점마다 나가는 간선 리스트를 두는 대신). 먼저 간선을 표현하는 구조체 $\rm edge$부터 구현을 시작합니다. 알고리즘의 입력은 수 $n$, $m$, 간선 리스트 $e$, 그리고 시작 정점 $v$입니다. 모든 정점에는 $0$부터 $n - 1$까지 번호가 매겨져 있습니다.
가장 간단한 구현¶
상수 $\rm INF$는 "무한대"를 나타내는 수로, 가능한 모든 경로 길이보다 크게 골라야 합니다.
struct Edge {
int a, b, cost;
};
int n, m, v;
vector<Edge> edges;
const int INF = 1000000000;
void solve()
{
vector<int> d(n, INF);
d[v] = 0;
for (int i = 0; i < n - 1; ++i)
for (Edge e : edges)
if (d[e.a] < INF)
d[e.b] = min(d[e.b], d[e.a] + e.cost);
// display d, for example, on the screen
}
if (d[e.a] < INF) 검사는 그래프에 음수 가중치 간선이 있을 때만 필요합니다. 이 검사가 없으면 아직 경로를 찾지 못한 정점에서 완화가 일어나 $\infty - 1$, $\infty - 2$ 같은 잘못된 거리가 생깁니다.
더 나은 구현¶
이 알고리즘은 조금 더 빠르게 만들 수 있습니다. 몇 단계 만에 이미 답을 얻는 경우가 많은데, 그러면 나머지 단계에서는 쓸모 있는 작업 없이 모든 간선을 방문하느라 시간만 낭비합니다. 그러므로 현재 단계에서 무언가 바뀌었는지를 알려 주는 플래그를 두고, 어떤 단계에서 아무것도 바뀌지 않았다면 알고리즘을 멈추도록 합시다. (이 최적화는 점근적 동작을 개선하지는 않습니다. 즉, 어떤 그래프에서는 여전히 $n-1$단계가 모두 필요합니다. 하지만 "평균적인" 경우, 즉 무작위 그래프에서는 알고리즘이 훨씬 빨라집니다.)
이 최적화를 적용하면 알고리즘의 단계 수를 직접 $n-1$로 제한할 필요가 대체로 없습니다 — 알고리즘은 필요한 만큼 단계를 수행한 뒤 스스로 멈춥니다.
void solve()
{
vector<int> d(n, INF);
d[v] = 0;
for (;;) {
bool any = false;
for (Edge e : edges)
if (d[e.a] < INF)
if (d[e.b] > d[e.a] + e.cost) {
d[e.b] = d[e.a] + e.cost;
any = true;
}
if (!any)
break;
}
// display d, for example, on the screen
}
경로 복원¶
이제 최단 경로의 길이만 구하는 것이 아니라 최단 경로 자체도 복원할 수 있도록 알고리즘을 수정하는 방법을 살펴봅시다.
이를 위해 배열 $p[0 \ldots n-1]$을 하나 더 만들고, 각 정점마다 그 정점의 "선행 정점", 즉 그 정점으로 가는 최단 경로에서 끝에서 두 번째 정점을 저장합니다. 실제로 임의의 정점 $a$까지의 최단 경로는 어떤 정점 $p[a]$까지의 최단 경로 끝에 $a$를 덧붙인 것입니다.
알고리즘이 같은 논리로 동작한다는 점에 주목하십시오. 알고리즘은 한 정점까지의 최단 거리가 이미 계산되었다고 가정하고, 그 정점에서 다른 정점들까지의 최단 거리를 개선하려고 시도합니다. 따라서 개선이 일어나는 시점에 $p[ ]$, 즉 이 개선이 일어난 출발 정점만 기억해 두면 됩니다.
다음은 주어진 노드 $t$까지의 최단 경로 복원을 포함한 Bellman-Ford 구현입니다:
void solve()
{
vector<int> d(n, INF);
d[v] = 0;
vector<int> p(n, -1);
for (;;) {
bool any = false;
for (Edge e : edges)
if (d[e.a] < INF)
if (d[e.b] > d[e.a] + e.cost) {
d[e.b] = d[e.a] + e.cost;
p[e.b] = e.a;
any = true;
}
if (!any)
break;
}
if (d[t] == INF)
cout << "No path from " << v << " to " << t << ".";
else {
vector<int> path;
for (int cur = t; cur != -1; cur = p[cur])
path.push_back(cur);
reverse(path.begin(), path.end());
cout << "Path from " << v << " to " << t << ": ";
for (int u : path)
cout << u << ' ';
}
}
여기서는 정점 $t$에서 시작하여 선행 정점이 없는 시작 정점에 도달할 때까지 선행 정점들을 따라가며, 경로상의 모든 정점을 리스트 $\rm path$에 저장합니다. 이 리스트는 $v$에서 $t$까지의 최단 경로이지만 역순으로 되어 있으므로, $\rm path$에 대해 $\rm reverse()$ 함수를 호출한 다음 경로를 출력합니다.
알고리즘의 증명¶
먼저, 도달할 수 없는 모든 정점 $u$에 대해서도 알고리즘이 올바르게 동작하여 레이블 $d[u]$가 무한대로 유지된다는 점에 주목하십시오(Bellman-Ford 알고리즘은 시작 정점 $v$에서 도달 가능한 모든 정점까지의 어떤 경로를 찾게 되며, 나머지 다른 정점들에 대해서는 완화가 결코 일어나지 않기 때문입니다).
이제 다음 명제를 증명해 봅시다: $i_{th}$ 단계를 실행한 후, Bellman-Ford 알고리즘은 간선 수가 $i$를 넘지 않는 모든 최단 경로를 올바르게 찾습니다.
다시 말해, 임의의 정점 $a$에 대해 그 정점까지의 최단 경로의 간선 수를 $k$라고 합시다(그러한 경로가 여러 개라면 아무것이나 택해도 됩니다). 이 명제에 따르면, 알고리즘은 $k_{th}$ 단계 이후에 정점 $a$까지의 최단 경로를 찾는다는 것을 보장합니다.
증명: 시작 정점 $v$에서 경로가 존재하는 임의의 정점 $a$를 생각하고, 그 정점까지의 최단 경로 $(p_0=v, p_1, \ldots, p_k=a)$를 생각해 봅시다. 첫 번째 단계 이전에 정점 $p_0 = v$까지의 최단 경로는 이미 올바르게 구해져 있습니다. 첫 번째 단계 동안 알고리즘은 간선 $(p_0,p_1)$을 검사하였으므로, 첫 번째 단계 이후 정점 $p_1$까지의 거리는 올바르게 계산되었습니다. 이 논증을 $k$번 반복하면 $k_{th}$ 단계 이후 정점 $p_k = a$까지의 거리가 올바르게 계산됨을 알 수 있으며, 이것이 우리가 증명하고자 한 것입니다.
마지막으로 주목할 점은 어떤 최단 경로도 $n - 1$개보다 많은 간선을 가질 수 없다는 것입니다. 따라서 알고리즘은 $(n-1)_{th}$ 단계까지만 진행하면 충분합니다. 그 이후에는 어떤 완화도 어느 정점까지의 거리를 개선하지 않음이 보장됩니다.
음수 사이클이 있는 경우¶
지금까지 위에서는 그래프에 음수 사이클이 없다고 가정하였습니다(정확히 말하면, 우리가 관심을 두는 것은 시작 정점 $v$에서 도달 가능한 음수 사이클이며, 도달할 수 없는 사이클에 대해서는 위 알고리즘에서 달라지는 것이 없습니다). 음수 사이클이 존재하는 경우에는 이 사이클에 속한 모든 정점까지의 거리와 이 사이클에서 도달 가능한 정점들까지의 거리가 정의되지 않는다는 사실 때문에 추가적인 문제가 생깁니다 — 이 거리들은 음의 무한대 $(- \infty)$여야 합니다.
Bellman-Ford 알고리즘이 이 사이클의 모든 정점과 그 사이클에서 도달 가능한 정점들 사이에서 끝없이 완화를 수행할 수 있다는 것은 쉽게 알 수 있습니다. 따라서 단계 수를 $n - 1$로 제한하지 않으면, 알고리즘은 이 정점들까지의 거리를 계속 개선하면서 무한히 실행됩니다.
따라서 우리는 시작 정점 $v$에서 도달 가능한 음수 가중치 사이클의 존재 판정 기준을 얻습니다: $(n-1)_{th}$ 단계 이후 알고리즘을 한 단계 더 실행했을 때 완화가 한 번이라도 더 일어난다면 그래프에는 $v$에서 도달 가능한 음수 가중치 사이클이 존재하며, 그렇지 않다면 그러한 사이클은 존재하지 않습니다.
또한 이러한 사이클이 발견되면, Bellman-Ford 알고리즘을 수정하여 이 사이클을 그 안에 포함된 정점들의 수열로 복원할 수 있습니다. 이를 위해서는 $n_{th}$ 단계에서 완화가 일어난 마지막 정점 $x$를 기억해 두는 것으로 충분합니다. 이 정점은 음수 가중치 사이클 위에 있거나, 그 사이클에서 도달 가능한 정점입니다. 음수 사이클 위에 있음이 보장되는 정점을 얻으려면, 정점 $x$에서 시작하여 선행 정점을 따라 $n$번 이동하십시오. 이렇게 하면 음수 사이클 위에 있음이 보장되는 정점 $y$에 도달하게 됩니다. 이 정점에서 출발하여 선행 정점을 따라 같은 정점 $y$로 다시 돌아올 때까지 이동해야 합니다(음수 가중치 사이클에서의 완화는 순환적으로 일어나므로 반드시 돌아오게 됩니다).
구현:¶
void solve()
{
vector<int> d(n, INF);
d[v] = 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] < INF)
if (d[e.b] > d[e.a] + e.cost) {
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 from " << v;
else {
int y = x;
for (int i = 0; i < n; ++i)
y = p[y];
vector<int> path;
for (int cur = y;; cur = p[cur]) {
path.push_back(cur);
if (cur == y && path.size() > 1)
break;
}
reverse(path.begin(), path.end());
cout << "Negative cycle: ";
for (int u : path)
cout << u << ' ';
}
}
음수 사이클이 존재하기 때문에, 알고리즘을 $n$번 반복하는 동안 거리 값이 음수 방향으로 크게 내려갈 수 있습니다($-n m W$ 정도 크기의 음수까지 내려갈 수 있으며, 여기서 $W$는 그래프에 있는 가중치의 절댓값 중 최댓값입니다). 따라서 코드에서는 다음과 같이 정수 오버플로를 막기 위한 추가 조치를 취했습니다:
d[e.b] = max(-INF, d[e.a] + e.cost);
위 구현은 어떤 시작 정점 $v$에서 도달 가능한 음수 사이클을 찾습니다. 하지만 알고리즘을 수정하여 그래프에 있는 임의의 음수 사이클을 찾도록 할 수도 있습니다. 이를 위해서는 모든 거리 $d[i]$를 무한대가 아닌 0으로 설정해야 합니다. 이는 마치 모든 정점에서 동시에 최단 경로를 찾는 것과 같으며, 음수 사이클 검출의 정확성에는 영향을 주지 않습니다.
이 주제에 대한 자세한 내용은 별도의 글 그래프에서 음수 사이클 찾기를 참고하십시오.
최단 경로 고속 알고리즘(Shortest Path Faster Algorithm, SPFA)¶
SPFA는 모든 완화 시도가 성공하지는 않는다는 사실을 활용하는 Bellman-Ford 알고리즘의 개선판입니다. 핵심 아이디어는 완화되었으면서 아직 이웃을 더 완화할 수 있는 정점들만 담는 큐를 만드는 것입니다. 그리고 어떤 이웃을 완화할 수 있을 때마다 그 정점을 큐에 넣어야 합니다. 이 알고리즘도 Bellman-Ford처럼 음수 사이클을 검출하는 데 사용할 수 있습니다.
이 알고리즘의 최악의 경우는 Bellman-Ford와 같은 $O(n m)$이지만, 실제로는 훨씬 빠르게 동작하며 평균적으로 $O(m)$에 동작한다고 주장하는 사람들도 있습니다. 하지만 이 알고리즘은 결정론적이므로 알고리즘이 $O(n m)$에 동작하게 만드는 반례를 쉽게 만들 수 있다는 점에 주의하십시오.
구현할 때 주의해야 할 점이 몇 가지 있는데, 예를 들어 음수 사이클이 있으면 알고리즘이 끝나지 않고 영원히 계속된다는 점입니다. 이를 피하려면 각 정점이 완화된 횟수를 저장하는 카운터를 두고, 어떤 정점이 $n$번째로 완화되는 즉시 알고리즘을 멈추면 됩니다. 또한 정점이 이미 큐에 들어 있다면 다시 큐에 넣을 이유가 없다는 점에 유의하십시오.
const int INF = 1000000000;
vector<vector<pair<int, int>>> adj;
bool spfa(int s, vector<int>& d) {
int n = adj.size();
d.assign(n, INF);
vector<int> cnt(n, 0);
vector<bool> inqueue(n, false);
queue<int> q;
d[s] = 0;
q.push(s);
inqueue[s] = true;
while (!q.empty()) {
int v = q.front();
q.pop();
inqueue[v] = false;
for (auto edge : adj[v]) {
int to = edge.first;
int len = edge.second;
if (d[v] + len < d[to]) {
d[to] = d[v] + len;
if (!inqueue[to]) {
q.push(to);
inqueue[to] = true;
cnt[to]++;
if (cnt[to] >= n)
return false; // negative cycle
}
}
}
}
return true;
}
온라인 저지의 관련 문제¶
Bellman-Ford 알고리즘으로 풀 수 있는 문제 목록입니다:
- E-OLYMP #1453 "Ford-Bellman" [난이도: 하]
- UVA #423 "MPI Maelstrom" [난이도: 하]
- UVA #534 "Frogger" [난이도: 중]
- UVA #10099 "The Tourist Guide" [난이도: 중]
- UVA #515 "King" [난이도: 중]
- UVA 12519 - The Farnsworth Parabox
그래프에서 음수 사이클 찾기 글의 문제 목록도 참고하십시오. * CSES - High Score * CSES - Cycle Finding