벨만-포드 개념

벨만 포드 알고리즘은 가중치가 존재하는 그래프에서 최단 경로를 구하고자 할 때 사용할 수 있는 알고리즘이다.

보통 위와 같은 유형의 문제를 풀기 위해 다익스트라 알고리즘을 먼저 학습한다.

결론부터 말하자면 다익스트라 알고리즘의 경우 음수 간선이 존재하는 경우 문제를 해결하지 못 할 수 있다.


다익스트라 음수 간선

위에서 다익스트라의 경우 음수 간선이 존재하면 문제를 해결하지 못한다고 하지 않았고 못 할 수 도 있다고 했다.

아래의 그래프를 통해 자세히 이해해보자.

출처 : https://8iggy.tistory.com/153

 

  • 단순한 음의 간선 : 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;

이 조건문은 왜 필요한지 이해해 보자.

출처 : https://yabmoons.tistory.com/365

★ 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)에 비해 느리지만

음수의 간선이 주어질 경우 다익스트라를 대체할 수 있는 알고리즘이다.