[그래프] Graph 8: 벨만-포드 최단 경로 알고리즘

1. 벨만 포드 알고리즘(Bellman-Ford)

 

다익스트라는 한 시작점의 최단 거리들을 구하는 알고리즘이지만

 

음수 간선이 있는 경우 정당성이 보장되지 않는다.

 

 

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

 

이것은 음수 간선이 있는 그래프에 대해서도 최단 경로를 찾을 수 있으며,

 

음수 사이클의 여부 또한 알 수 있다.

 

 

 

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

 

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

 

그러므로 수행 과정에서 각 정점까지의 최단 거리의 상한을 담은 배열 upper[]을 유지해야한다.

 

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

 

 

 

 

 

2. 벨만-포드의 동작 과정

 

알고리즘이 시작할 때는 그래프의 구조에 대해 아는 것이 하나도 없다.

 

따라서 시작점인 s에 대해 upper[s] = 0 으로 초기화하고, 나머지 원소들은 모두 아주 큰 수 인 inf로 초기화 한다.

 

벨만-포드 알고리즘은 이 예측 값을 실제 최단 거리에 더 가깝게 갱신하기 위해 최단 거리의 특성을 이용한다.

 

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

시작점에서 u 와 v까지의 최단 거리 는 항상 위의 식을 만족해야한다.

 

이 속성을 이용하면 upper의 값을 좀더 실제 최단 거리에 가깝게 보정할 수 있다.

 

upper[u] + w(u, v) < upper[v]라고 해보자

 

u까지 가는 최단 거리는 항상 upper[u]이거나 그보다 짧다.

 

그 뒤에 (u, v)를 붙인 경로의 길이는 최대 upper[u] + w(u, v)라는 사실을 알 수 있고,

 

따라서 upper[v]를 upper[u] + w(u, v)로 줄여도 된다.

 

이와 같은 과정을 통해 upper[v]를 감소하는 작업을 (u, v)를 따라 완화(relax)한다고말한다

 

벨만 포드 알고리즘은 이와 같은 완화 과정을 모든 간선에 대해 반복적으로 실행하며 

 

성공할 때마다 upper는 줄어들고, 실제 우리가 원하는 최단 거리에 가까워진다.

 

 

 

3. 종료 조건과 정당성 증명

 

upper가 실제 최단거리가 되는지 확인해보자

 

s에서 어떤 정점 u까지의 최단 경로가 다음과 같다고 한다.

 

s - a - b - c - u

s - a - b - c - u

s - a - b - c - u

s - a - b - c - u

s - a - b - c - u

 

 

최단 경로가 보장된 정점은 빨간색으로 표시되었다.

 

처음 upper[s] = 0 이므로 s에만 색이 있다.

 

모든 간선을 순회하면서 한 번씩 완화를 시도해보자

 

모든 간선에 대해 완화를 시도했으므로, (s, a)에 대한 완화도 이루어진다.

 

upper[a] <= upper[s] + w(s, a)

upper[a] <= w(s, a)

 

하지만 여기서 w(s, a)는 항상 최단 거리여야 한다. 이것보다 짧은 경로가 있었다면 최단 경로라는 가정에 어긋나기 때문이다.

 

따라서 upper[a] = w(s, a)이며 a에 대한 최단 거리를 찾았다는 것을 알 수 있다.

 

그 후 또 다시 완화작업을 한다. 그로인해 upper[b]가 최단이 되고 결국 upper[u] = dist[u] 가 된다.

 

 

이로인해 완화 작업을 x번하면 x개 이하의 간선을 사용하는 최단 경로들을 전부 찾을 수 있다는 것을 알 수 있다.

 

음수 사이클이 없는 그래프에서 최단 경로가 한 정점을 두 번 지나는 일은 없다.

 

그러므로 간선 수의 상한은 다음과 같다.

 

최단 경로는 최대 |V|개의 정점을 갖기 때문에 최대 |V|-1 개의 간선을 가질 수 있다.

 

따라서 모든 간선에 대해 완화 과정은 전체 |V|-1번이면 충분하다.

 

 

 

 

4. 음수 사이클의 판정

 

벨만-포드 알고리즘을 간단히 변경해서 음수 사이클의 여부를 파악할 수 있다.

 

|V|-1 번 완화하는 대신 |V| 번 완화하는 것이다.

 

그래프에 음수 사이클이 없다면 최단거리는 한번 완화를 더 해도 그대로이다.

 

하지만 음수 사이클이 있는 경우 완화가 성공하여 값이 변하게된다.

 

 

s  ->  a  ->  b  ->  s

  10      -21      10

 

위 사이클은 전체 가중치가 -1 인 음수 사이클이다. 이 그래프를 3번 완화를 한 뒤 완화가 실패했다고 가정해보자

 

upper[a] <= upper[s] + 10

upper[b] <= upper[a] - 21

upper[s] <= upper[b] + 10

 

그러면 위 세 부등식을 만족해야한다. 이를 전부 좌변 우변 더해보면 다음과 같다

 

upper[a] + upper[b] + upper[c] <= upper[a] + upper[b] + upper[c]  -1

 

0 < = -1

 

이 식은 모순이므로 세 간선 중 하나는 항상 완화가 성공해야한다는 사실을 알 수 있다.

 

 

 

5. 구현

 

모든 간선을 검사하는 중첩 반복문에 의해 지배된다

 

가장 바깥에 있는 for문은 |V| 번 수행되고.

 

안의 두 for문은 모든 간선을 순회하므로 O(|E|)번 수행되므로 전체 시간 복잡도는 O(|V||E|)가 된다.

 

 

int V;
 
vector<pair<int, int> > adj[MAX_V];
 
vector<int> bellmanFord(int src)
{
    vector<int> upper(V, INF);
    upper[src] = 0;
    bool updated;
 
    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;
                if(upper[there] > upper[here] + cost)
                {
                    upper[there] = upper[here] + cost;
                    updated = true;
                }
            }
        if(!updated) break;
    }
    if(updated) upper.clear();
    return upper;
}

 

 

6. 실제 경로 계산하기

 

벨만 포드 알고리즘을 수행하는 과정에서 각 정점을 마지막으로 완화시킨 간선들을 모으면 스패닝 트리를 얻을 수 있다.

 

각 정점을 마지막으로 완화 시킨 간선들은 항상 최단 경로 위에 있기 때문에, 각 정점에서 부터 루트까지 거슬러 올라가면

 

그 경로가 최단 경로가 된다.

 

 

 

 

7. 주의할 점

 

s로부터 어떤 정점 u로 가는 경로가 존재하는지를 확인할때 만약

 

음수 사이클이에 u가 있지만 s와 연결이 안되어있을때

 

upper[u] == inf 가 아니라

 

적당히 큰 값 M에 대해  !(upper[u] < inf - M) 인지를 확인해야한다.

 

그 이유는 완화가 수행될수록 음수 사이클로 인해 upper[u]는 점점 작아지기 때문이다

 

 

- 알고리즘 문제해결전략 947p

 

[그래프] TIMETRIP 시간여행