벨만-포드 (Bellman-Ford)

벨만-포드 (Bellman-Ford) ?

• 다익스트라 알고리즘은 한 시작점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘 중 가장 유용한 알고리즘이다.
  • 하지만, 음수 간선이 있는 그래프의 경우 그 정당성이 보장되지 않는다.
  • 벨만-포드의 최단 경로 알고리즘은 이와 같은 문제점을 해결하는 알고리즘이다.
• 벨만-포드는 다익스트라와 동일한, 단일 시작점 최단 경로 알고리즘이지만, 음수 간선이 있는 그래프에 대해서도 최단 경로를 찾을 수 있으며 그래프에 음수 사이클이 있어서 최단 거리가 제대로 정의되지 않을 경우, 이 또한 알려준다.
  
  • 시작점에서 각 정점까지 가는 최단 거리의 상한을 적당히 예측한 뒤 예측 값과 실제 최단 거리 사이의 오차를 반복적으로 줄여가는 방식으로 동작한다.
  • 이것은 BFS를 기반으로 한 번에 하나씩 한 정점의 최단 거리를 확정해 가는 다익스트라와는 다르다.
• 벨만-포드는 수행 과정에서 각 정점까지의 최단 거리의 상한을 담은 배열 upper[] 를 유지한다.
  • 이 값은 알고리즘이 진행됨에 따라 점점 줄어들고, 알고리즘이 종료할 때는 실제 최단 거리를 담게 된다.

 

동작 과정

• 알고리즘이 시작할 때, 시작점에서 시작점까지의 최단 거리가 0이라는 사실 말고는 그래프의 구조에 대해 아는 것이 하나도 없다.
  • 따라서 upper[1] = 0으로 초기화하고, 나머지 원소들은 모두 큰 수인 \(\infty\) 로 초기화하자.
• 벨만-포드는 이 예측 값을 실제 최단 거리에 더 가깝게 갱신하기 위해 최단 거리의 특성을 이용한다.
  • 이 특성은 시작점에서 2와 3까지의 최단 거리 dist[2] 와 dist[3] 에 대해 다음 조건이 항상 참이라는 점이다.

$$dist[3] \, \le \, dist[2] + w(2, 3)$$

• 이 조건이 왜 항상 성립하는지를 아래 그림을 보고 확인해보자.

• 위 그림은 그래프의 일부인 두 정점을 나타낸다.
  • 이때 간선 (2, 3) 의 가중치가 30이고, dist[2] = 10, dist[3] = 50이라고 하자.
  • 하지만 이 상황은 모순이다.
    • dist[2] = 10 이라는 말은 1에서 2로 오는 길이 10짜리 경로가 있다는 말인데, 이 경로 뒤에 간선 (2, 3) 을 붙이면 길이 40인 경로를 얻을 수 있다.
    • 그러므로 3까지의 최단 거리 dist[3] 은 40보다 클 수 없다.
  • 앞의 조건은 이것을 수식으로 쓴 것이다.
• 이 속성을 이용하면 upper의 값을 좀더 실제 최단 거리에 가깝게 보정할 수 있다.
• upper[2] + w(2, 3) < upper[3] 인 상황을 생각해보자.
  • 2까지 가는 최단 거리는 항상 upper[2] 이거나 그보다 짧다.
  • 따라서 upper[3] 을 upper[3] - w(2, 3) 로 줄여도 될 것이다.
  • 이와 같은 과정을 통해 upper[3] 를 감소하는 작업을 (2, 3) 을 따라 완화 (Relax) 한다고 말한다.
• 벨만-포드는 이와 같은 완화 과정을 모든 간선에 대해 반복적으로 실행한다.
  • 완화가 성공할 때마다 upper는 줄어들고, 실제 우리가 원하는 최단 거리에 가까워진다.

 

종료 조건과 정당성의 증명

• 하지만 위와 같은 것들만으로는 제대로 된 알고리즘이라고 하기에 부족하다.
  • 이 과정을 몇 번이나, 그리고 어떤 순서로 완화를 해야 할까?
  • upper가 실제 최단 거리와 같아지는 때는 언제 일까?
  • 어떤 정점을 택하더라도 upper[2] = dist[2] 가 되도록 하는 완화 순서를 만들 수 있을까?

• 1에서 어떤 정점 2까지의 최단 경로가 위 그림의 (a) 와 같다고 하자.
  • upper[] 가 실제 최단 거리와 같음이 보장된 정점들은 동심원으로 표시한다.
  • 처음에는 upper[1] = 0이므로, 1만 점선으로 표시한다.
• 이제 모든 간선을 순회하면서 한 번씩 완화를 시도하면 무슨 일이 벌어질까?
  • 모든 간선에 대해 완화를 시도했으므로 (1, 4) 에 대한 완화도 이루어진다.
  • 따라서 이제 upper[4] \(\le\) upper[1] + w(1, 4) 가 항상 성립힌다.
  • 그런데 upper[1] = 0이기 때문에 upper[1] \(\le\) w(1, 4) 가 된다.
  • 그런데 w(1, 4) 는 1에서 4까지 가는 최단 거리여야 한다.
  • 이것보다 짧은 경로가 있다면 애초에 1-4-3-5-2가 2까지의 최단 경로가 아니게 되기 때문이다.
  • 따라서 upper[4] = w(1, 4) 이며 4에 대한 최단 거리를 찾았다는 것을 알 수 있다.
  • 이 상태를 위 그림 (b) 처럼 표현할 수 있다.
• 여기에서 다시 모든 간선에 대해 한 번씩 완화를 시도했다고 하자.
  • 위와 똑같은 과정을 거쳐 위 그림 (c) 와 같이 upper[3] 이 최단 거리를 담게 됨을 알 수 있다.
  • 이렇게 전체 과정을 네 번 반복하면 결과적으로 upper[2] = dist[2] 가 됨을 알 수 있다.
• 이것을 일반화하자면 모든 간선에 대해 완화를 시도하는 작업을 x번 반복하면 x개 이하의 간선을 사용하는 최단 경로들은 전부 찾을 수 있다는 이야기가 된다.
  • 따라서 모든 간선이 전부 완화가 실패할 때까지 반복하면 모든 최단 경로를 찾을 수 있다.

그러면 몇 번이나 반복을 해야 할지는 미리 알 수 없는 걸까?

• 음수 사이클이 없는 그래프에서 최단 경로가 한 정점을 두 번 지나는 일은 없다는 점을 떠올리면, 최단 경로가 포함하는 간선 수의 상한을 쉽게 알 수 있다.
  • 최단 경로는 최대 \(|V|\) 개의 정점을 갖기 때문에 잘 해야 \(|V|\) - 1 개의 간선을 가질 수 있다.
  • 따라서 모든 간선에 대한 완화 과정은 전체 \(|V|\) - 1 번이면 충분하다.
• 다익스트라와는 달리 벨만-포드의 증명에서는 각 간선이 음수가 아니라고 가정한 적이 없다.
  • 따라서 벨만-포드는 음수 간선이 존재하는 경우에도 최단 거리를 올바르게 계산해낼 수 있다.

 

음수 사이클의 판정

• 이 장의 처음에서 이야기했듯이, 그래프에 음수 사이클이 있을 때 최단 거리 문제는 제대로 정의되지 않는다.
  • 따라서 그래프에 음수 사이클이 존재할 경우 벨만-포드는 예외 없이 의미 없는 값을 반환하게 된다.
• 하지만 간단한 변형을 통해 벨만-포드가 음수 사이클의 존재 여부를 판정하도록 할 수 있다.
  • 이렇게 하면 음수 사이클이 있는 그래프가 입력으로 주어졌을 때 의미 없는 값을 반환하는 대신 음수 사이클이 존재한다는 오류를 반환할 수 있게 된다.
• 음수 사이클의 존재 여부를 판정하려면 \(|V|\) - 1 번 모든 간선에 대해 완화를 시도하는 대신 \(|V|\) 번 완화를 시도하면 된다.
  • 그래프에 음수 사이클이 없다면 \(|V|\) - 1 번 만의 반복으로 모든 최단 거리를 찾아내기 때문에, 마지막 반복의 완화는 전부 실패하게 된다.
  • 반면 음수 사이클이 있다면 \(|V|\) 번째 반복에서도 항상 완화가 한 번은 성공한다는 점을 증명할 수 있다.

간단한 예시

• 아래 그림의 그래프에서 1-2-3-1은 전체 가중치가 -1인 음수 사이클이다.
  • 이때 세 번 완화를 한 뒤 완화가 전부 실패한다고 가정해 보자.
• 그러려면 다음과 같은 세 개의 부등식이 성립해야 한다.

\(upper[2] \le upper[1] + 10\)

\(upper[3] \le upper[2] - 21\)

\(upper[1] \le upper[3] + 10\)

음수 사이클의 판정

• 부등식들의 좌변과 우변을 각각 모두 더해 보면 다음과 같은 식을 얻을 수 있다.

$$upper[1] + upper[2] + upper[3] \le upper[1] + upper[2] + upper[3] - 1$$

• 양쪽에 중복된 항들을 지워보면 \(0 \le -1\) 을 얻을 수 있다.
  • 당연히 이 식은 모순이므로, 세 간선 중 하나에서는 항상 완화가 성공한다는 사실을 알 수 있다.
  • 이 과정은 모든 음수 사이클에 대해 쉽게 일반화할 수 있다.

 

구현

• 아래 코드는 음수 사이클의 존재 여부 확인을 포함하는 벨만-포드 알고리즘의 구현을 보여준다.
  • \(|V|\) - 1 번 완화를 반복하는 대신 \(|V|\) 번 반복하고, 마지막 반복에서도 완화가 성공했을 경우 배열 값들을 초기화 해주는 것을 볼 수 있다.

public static class Element {
    int idx, dist;
 
    public Element(int idx, int dist) {
        this.idx = idx;
        this.dist = dist;
    }
}

 

public static void BellmanFord(int start) {
    boolean updated = false;
 
    dist[start] = 0;
 
    for (int i = 1; i <= V; i++) {
        updated = false;
        for (int from = 1; from <= V; from++) {
            for (Element to : graph[from]) {
                if (dist[to.idx] > dist[from] + to.dist) {
                    dist[to.idx] = dist[from] + to.dist;
                    updated = true;
                }
            }
        }
 
        if (!updated)
            break;
    }
 
    if (updated)
        Arrays.fill(dist, Integer.MAX_VALUE);
}

 

시간 복잡도

• 벨만-포드의 수행 시간은 모든 간선을 검사하는 중첩 반복문에 의해 지배된다.
  • 가장 바깥에 있는 for문은 \(|V|\) 번 수행되고, 내부의 두 for문은 모든 간선을 순회하므로 \(O(|E|)\) 번 수행된다.
  • 따라서 벨만-포드 알고리즘의 전체 시간 복잡도는 \(O(|V||E|)\) 이다.

 

실제 경로 계산하기

• 벨만-포드 알고리즘을 수행하는 과정에서 각 정점을 마지막으로 완화시킨 간선들을 모으면 스패닝 트리를 얻을 수 있다.
  • 각 정점을 마지막으로 완화시킨 간선들은 항상 최단 경로 위에 있기 때문에, 각 정점에서부터 스패닝 트리의 루트인 시작점까지 거슬러 올라가는 경로는 항상 시작점에서 해당 경로까지의 최단 경로이다.
• 따라서 BFS나 다익스트라와 비슷한 방식으로 실제 정점의 목록을 계산할 수 있다.

 

빠지기 쉬운 함정

• 벨만-포드를 실행한 뒤 1로부터 어떤 정점 2로 가는 경로가 존재하는지를 확인하고 싶으면 어떻게 해야할까?
  • 맨 처음에 upper[2] = \(\infty\) 로 초기화했으니, 벨만-포드가 종료한 후에 upper[2] = \(\infty\) 만 아니면 경로가 존재한다고 판단하는 프로그램을 짜기 쉽다.
  • 하지만 음수 가중치가 있다면 얘기가 달라진다.
• 아래 그림의 그래프에 대해 벨만-포드를 수행했다고 하자.
  • 두 간선 (a, b) 와 (b, a) 에 대해 순서대로 완화를 수행했다고 하면 upper[b] = \(\infty\) - 2, upper[a] = \(\infty\) - 1가 됨을 알 수 있다.
  • 완화가 반복될수록 두 값은 작아지기 때문에 따라서 2로 가는 경로가 존재하는지 확인하기 위해서는 적당히 큰 값 \(M\) 에 대해 upper[2] \(\le \infty - M\) 인지를 확인해야 한다.

벨만-포드 알고리즘을 사용할 때 주의할 점

 

Reference

• 도서 : 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략