7. 최단 경로 알고리즘 - Bellman-Ford 알고리즘

벨만-포드 알고리즘은 다익스트라 알고리즘과 같이 단일 시작점 최단 경로 알고리즘이지만,

음수 간선이 있는 그래프에 대해서도 최단 경로를 찾을 수 있다.

또한, 음수 사이클이 있는 경우 사이클이 존재한다는 사실도 확인할 수 있다.

벨만-포드 알고리즘은 시작점에서 각 정점까지 가는 최단거리의 상한을 적당히 예측한 뒤, 

예측값과 실제 최단 거리 사이의 오차를 반복적으로 줄여가는 방식으로 동작한다.

각 정점까지의 최단 거리의 상한을 담는 배열 upper[]가 존재한다.

이 값들은 알고리즘이 진행됨에 따라 점점 줄어들고, 마지막에는 실제 최단 거리를 담게 된다.

어떤 정점까지의 최단 거리를 dist[] 라고 할 때,

두 정점 u, v에 대해서 항상 다음과 같은 속성이 만족한다. 물론 간선 (u, v) 가 존재한다는 가정이다.

dist[v] <= dist[u] + w(u, v)

여기서 w(u, v) 는 간선 (u, v)의 가중치이며,

시작점에서 u로 가는 최단 거리가 dist[u]이고, u와 v는 연결되어 있으므로 dist[v]는 적어도 두 값을 더한 값 이하의 최단 거리를 가진다.

이 속성을 이용하면 upper[v] > upper[u] + w(u, v) 인 상황에서 upper[v]의 값을 upper[u] + w(u, v) 로 감소시킬 수 있다.

이같은 과정을 통해 upper[]를 감소하는 과정을 완화한다고 말한다.

벨만-포드 알고리즘은 이런 완화 과정을 모든 간선에 대해 반복적으로 실행하여 최종 최단 거리를 찾아낸다.

우선 모든 정점에 대해 각 정점에 연결되어 있는 모든 정점의 upper값을 완화 시도한다.(모든 간선에 대해 완화를 시도)

이 과정이 끝나면 시작점의 upper값은 항상 0 이므로, 시작점과 연결되어 있는 정점들 중 하나 이상이 최단 거리를 확정하게 된다.

다시 모든 간선에 대한 완화 과정을 반복하면, 앞서 최단 거리가 확정된 정점들과 연결된 정점들 중 하나 이상이 최단 거리를 확정하게 된다.

이런 식으로 한번의 완화 과정에서 최단 경로 스패닝 트리의 하나의 간선을 완성한다고 하면,

정점이 v개 일 때, 완화 과정을 최대 v-1번 반복하면 시작점에서 모든 정점까지의 최단 거리를 구할 수 있다.

음수 사이클의 판정

그래프에 음수 사이클이 있는 경우 최단 경로가 제대로 정의되지 않는다.

따라서 그래프에 음수 사이클이 존재하는 경우 벨만-포드 알고리즘도 의미없는 값을 반환하게 된다.

하지만 간단한 변형을 통해 의미 없는 값이 아닌, 음수 사이클이 존재한다는 오류를 반환할 수 있게 된다.

그래프에서 음수 사이클이 존재하는 경우, v번째 완화 과정에서도 완화가 적어도 한번은 성공하게 된다.

음수 사이클은 해당 사이클 경로를 반복해서 돌수록 경로 거리 값이 감소하기 때문이다.

따라서 완화 과정을 v번 반복하였는데 완화된 값이 있다면 음수 사이클이 존재한다고 판단할 수 있다.

// 벨만-포드 알고리즘

int v;  // 정점의 개수

vector< pair<int, int> > adj[MAX_V];  // 각 정점에 연결된 (정점의 번호, 간선의 가중치) 쌍 배열

vector<int> bellmanFord(int src){

vector<int> upper(v, INF);  // 모든 정점의 상한선을 무한대로 초기화

upper[src] = 0;

bool updated;  // 각 완화 과정에서 한번이라도 완화에 성공하면 true를 가진다.

for(int iter = 0; iter < v; iter++){

updated = false;

for(int here = 0; here < v; here++){

for(int i = 0; i < adj[here].size(); i++){

int there = adj[here][i].first;

int cost = adj[here][i].second;

// (here, there) 간선에 대하여 완화 시도

if(upper[there] > upper[here] + cost){

upper[there] = upper[here] + cost;

updated = true;

}

}

}

if(!updated) break;  // v-1번 반복하지 않아도 중간에 완화를 모두 실패하면 이미 최단 거리 다 구한 것이므로 종료

}

// v번 완화 과정 반복 후에도 완화된 것이 있다면 음수 사이클 존재하는 것

if(updated) return vector<int>();

return upper;

}

위 코드는 모든 간선에 대해 완화 과정을 v번 반복하므로, 시간 복잡도가 O(|V||E|) 이다.