[Algorithm] 벨만포드(Bellman-Ford) 알고리즘
Bellman-Ford 알고리즘이란?
Bellman-Ford 알고리즘이란, 한 노드에서 다른 노드까지의 최단거리를 구하는 알고리즘입니다. 벨만포드 알고리즘 외에 최단거리를 구하는 알고리즘은 여럿 있지만 벨만포드는 가중치가 음수 일 때도 사용이 가능합니다. 하지만 다익스트라 알고리즘에 비해 느리므로 가중치가 모두 양수일 경우에는 굳이 벨만포드 알고리즘을 사용할 필요가 없습니다.
음수간선
음수간선이 있을 경우 어떠한 문제가 생길지 알아보도록 하겠습니다.
아래 그래프에서 s 에서 출발하여 g 로 도착하는 경우를 생각해봅시다.
-
s -> a -> b -> g
이 경우도 물론 음수간선이 존재합니다. 하지만 문제가 되는 경우는 없습니다. 3+(-4)+4 로 가중치 3으로 도착할 수 있습니다.
-
s -> c -> d -> g
음수간선이 사이클로 존재합니다. 하지만 이 경우 사이클을 순환할 이유가 없습니다. c->d->c->d ... 을 반복할수록 오히려 가중치만 늘어나게 됩니다.
-
s -> e -> f -> g
이 경우 문제가 생깁니다. 음수간선이 사이클로 존재하면서 사이클을 순환할수록 가중치는 감소하게 됩니다. 따라서 이 경우에는 해당 사이클을 순환하고 g 에 도착하는 건 가중치는 낮더라고 실절적인 최단경로라고 볼 수 없습니다.
위 경우를 보고 다음과 같은 결론을 내릴 수 있습니다.
최단경로는 순환을 포함해서는 안되므로 경로의 길이는 최대 |V|-1 이다.
알고리즘
벨만포드에 대한 수도코드를 보면서 알고리즘을 이해해보도록 하겠습니다.
최단경로는 순환을 포함해서는 안되므로 경로의 길이는 최대 |V|-1 개 입니다. 그리고 각 정점에 대해서 정점과 연결된 모든 간선을 확인하며 RELAX 를 해줍니다.
RELAX 는 해당 정점에 대해서 더 낮은 가중치로 도달할 수 있는 경우, 그 값을 갱신해주는 것을 말합니다.
그 후 다시 모든 간선에 대해서 RELAX 를 검사해줍니다. 만약 그렇다면 위 그래프 이미지에서 s->e->f->g 와 같이 음수간선으로 인한 사이클이 있다는 의미입니다. 따라서 false 를 반환해주고 아니라면 true 를 반환해주도록 합니다.
시간복잡도
위에서 봤듯이 경로의 길이는 최대 |V|-1 입니다. 즉 |V|-1 까지만 반복해주고 그 이상이 된다면 사이클이 생기므로 멈춰줘야합니다. 각 반복에 대해서는 해당 정점과 연결되어 있는 모든 간선을 탐색해주어야 합니다. 따라서 시간복잡도는 O(|V||E|)가 됩니다.
이 때 그래프의 간선이 많으면 보통 정점의 개수의 제곱 개 정도 존재하게 됩니다. 따라서 E = V^2 , O(V^3) 의 복잡도라고 볼 수 있습니다. 다익스트라가 O(V^2) 인데 비해 복잡도가 높습니다. 따라서 음수 가중치가 있어서 벨만포드를 사용해야하는 경우가 아니라면 다익스트라를 사용하는게 일반적으로 더 빠릅니다.
구현
https://www.acmicpc.net/problem/11657
백준에 벨만포드를 사용하는 문제가 있어 해당 문제의 풀이입니다.
#include <iostream>
#include <vector>
using namespace std;
#define INF 987654321
int dist[502];
vector<pair<int,int>> v[502];
int main(){
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
// 정점,간선의 수
int N,M;
cin >> N >> M;
bool cycle = false;
for (int i=0;i<M;i++){
int node1,node2,w;
cin >> node1 >> node2 >> w;
v[node1].push_back(make_pair(node2, w));
}
for (int i=1;i<=N;i++){
dist[i] = INF;
}
dist[1] = 0;
// 경로의 길이는 N-1 이고 N 이 된다면 음수사이클 생긴다.
for (int i=1;i<=N;i++){
// 모든 정점에 대해서 모든 간선을 탐색한다.
for (int j=1;j<=N;j++){
for (auto &n : v[j]){
// 방문되지 않은 지점에서 출발은 SKIP
if (dist[j] != INF && dist[n.first]>n.second + dist[j]){
dist[n.first] = n.second + dist[j];
if (i==N) cycle = true;
}
}
}
}
if (cycle) cout << "-1\n";
else {
for (int i=2;i<=N;i++){
if (dist[i] == INF) cout << "-1\n";
else cout << dist[i] << "\n";
}
}
}