벨만-포드 개념
벨만 포드 알고리즘은 가중치가 존재하는 그래프에서 최단 경로를 구하고자 할 때 사용할 수 있는 알고리즘이다.
보통 위와 같은 유형의 문제를 풀기 위해 다익스트라 알고리즘을 먼저 학습한다.
결론부터 말하자면 다익스트라 알고리즘의 경우 음수 간선이 존재하는 경우 문제를 해결하지 못 할 수 있다.
다익스트라 음수 간선
위에서 다익스트라의 경우 음수 간선이 존재하면 문제를 해결하지 못한다고 하지 않았고 못 할 수 도 있다고 했다.
아래의 그래프를 통해 자세히 이해해보자.
- 단순한 음의 간선 : s -> a -> b -> g 경로에 -4(a -> b) 음의 간선이 있어도 문제가 발생하지 않음
- 순환하지 않는 싸이클 : s -> c > -> d 경로 이후 d->c로 가는 경우 -3 음의 간선이 있지만 현재 dist[c]의 값인 5보다 d-> c로 이동하여 갱신될 dist[c] = dist[d] - 3 = 11- 3 = 8 의값이 더 작지 않기 때문에 정점 d와 c사이에 무한 순환이 발생하지 않음
- 순환하는 싸이클 : s -> e -> f -> e -> f -> e... -6(f->e) 음의 간선(-6)에 의해 최소값이 계속 갱신되며 무한 순환이 발생하고 따라서 문제가 발생함!!!
이처럼 음의 간선이 문제를 일으키지 않을 수 도 있지만 순환하는 싸이클이 발생할 경우 최단 경로가 무한히 갱신되기 때문에 다익스트라 알고리즘으로는 문제를 해결할 수 없다.
이러한 경우 벨만 포드 알고리즘을 사용하여 문제를 해결 할 수 있다.
벨만-포드 동작원리
1.출발 노드 설정(d[start] = 0)
2.모든 간선에 대해 최단 거리 갱신
3.2번 과정을 (V(정점의 개수) -1) 라운드 만큼 반복.
https://www.acmicpc.net/problem/11657
11657번: 타임머신
첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다.
www.acmicpc.net
구현 코드
#include<iostream>
#include<vector>
using namespace std;
#define INF 5000001
#define MAX 501
typedef long long ll;
int N, M, A, B, C;
ll dist[MAX];
vector<pair<ll, int>> edge[MAX];
void input() {
cin >> N >> M;
for (int i = 1; i <= N; i++) dist[i] = INF;
for (int i = 0; i < M; i++) {
cin >> A >> B >> C;
edge[A].push_back({ B, C });
}
}
bool bellman() {
dist[1] = 0;
bool isUpdated;
int next;
ll cost;
// N - 1 라운드 진행 후 N번째에서 순환 싸이클이 발생하는지 판별하기 보다
// N번 수행 중 어떠한 간선에서도 최소 값 갱신이 이뤄지지 않으면 멈추는 것이 효율적임
for (int i = 1; i <= N; i++) {
isUpdated = false;
for (int cur = 1; cur <= N; cur++) {
if (dist[cur] == INF) continue;
for (int j = 0; j < edge[cur].size(); j++) {
next = edge[cur][j].first;
cost = edge[cur][j].second + dist[cur];
if (dist[next] > cost) {
dist[next] = cost;
isUpdated = true;
}
}
}
// 특정 라운드 진행 중 어떠한 간선에서도 최단 거리 갱신이 이뤄지지 않았다는 것은
// 이미 음수 간선으로 인한 순환 싸이클이 발생하지 않았다는 것
// 따라서, 나머지 라운드를 진행할 필요 없음.
if (!isUpdated) return 1;
}
return 0;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
input();
if (bellman())
for (int i = 2; i <= N; i++) {
if (dist[i] != INF) cout << dist[i] << "\n";
else cout << -1 << "\n";
}
else cout << -1;
return 0;
}if (dist[cur] == INF) continue;
이 조건문은 왜 필요한지 이해해 보자.
★ 1번 정점을 한번이라도 방문한 정점이라 표시하기 위해서 Dist[1] = 0 으로 설정 후 탐색시작.
★ 간선 'A'에 의해서 '2'번 정점이 '3'으로 업데이트 Dist[2] = 3 (2번 정점은 한번이라도 계산된 정점이 되었다.)
★ 간선 'B'에 의해서 '3'번 정점이 '3'으로 업데이트. Dist[3] = 3 (3번 정점은 한번이라도 계산된 정점이 되었다.)
★ 간선 'C'에 의해서 '4'번 정점이 '1'로 업데이트. Dist[4] = 2 (4번 정점은 한번이라도 계산된 정점이 되었다.)
★ 간선 'D'에 의해서 '2'번 정점이 '-2'로 업데이트. Dist[2] = -2
★ 간선 'E'에 의해서 '4'번 정점이 '1'로 업데이트. Dist[4] = 1.
위 조건이 없는 경우 1번 정점에서 4번 정점으로의 최단 거리가 1번 정점에서 결코 도달할 수 없는 5번 정점으로 인해 잘못 된 최단 거리로 갱신 될 수 있음을 알 수 있다.
벨만포드 알고리즘은 특정 정점을 시작으로 도달 가능한 모든 정점으로의 최단 거리를 구하는 것이 목적임을 잊지말자.
시작 정점에서 방문가능한지 확실시 되지도 않은 정점에서 간선의 최단거리를 갱신하는 것은 잘못된 결과를 만들 수 있다
다익스트라 알고리즘과 상당부분 유사하여 개념을 이해하는데 큰 어려움은 없었지만
개인적으로 V-1라운드 만큼 진행한다는 부분을 납득하는데 조금 시간이 걸렸다.
아래 예시를 통해 V-1번 라운드를 반복하는 이유를 이해해보자.
위 처럼 노드가 일렬로 연결돼 있는 그래프가 주어진 경우 라운드를 한번만 진행한 결과를 살펴보자.
이 처럼 라운드를 한번만 진행할 시 4번 정점만 2(dist[4] = 2)로 갱신되고 나머지 정점은 최단 거리가 갱신되지 않는 것을 알 수 있다.
이는 1번 노드부터 N번 노드까지 순서대로 간선을 탐색하는데( for(int cur = 1; cur <= N; cur++) )
5번 시작 노드를 제외하고는 초기 상태인 INF값을 가지고 있어
if(dist[cur] = INF) continue; 조건을 만나 넘어가기 때문이다.
그리고 한번더 라운드를 진행해야 아래와 같이 3번 노드의 최단 거리가 갱신된다.
결국 위와 같이 최악의 그래프가 주어지는 경우 최대 V-1번의 라운드를 진행해야만 모든 정점의 최단거리가 갱신된다.
N-1번 라운드를 반복한 후 N번 째 라운드를 진행했을 때 최단 거리가 갱신되는 지점이 있다면
이는 음수 간선에 의한 순환 사이클이 발생한 것으로 판단할 수 있다.
벨만 포드의 시간복잡도는 O(V*E)로 다익스트라의 시간복잡도 O(V * logE)에 비해 느리지만
음수의 간선이 주어질 경우 다익스트라를 대체할 수 있는 알고리즘이다.