하나의 정점에서 출발했을 때, 다른 모든 정점으로의 최단 경로를 구하는 Algorithm이다.
다익스트라와의 차이점을 명확히 이해해야 한다.

  • 다익스트라 알고리즘과 다르게 DP에 가까운 방식의 알고리즘이다.
    • 따라서 다익스트라보다 시간 복잡도는 더 크다.
  • 다익스트라 알고리즘과 다르게 음의 가중치가 있어도 사용이 가능하다.

기본 원리

다익스트라 알고리즘은 “방문하지 않은 정점 중 최단거리인 정점” 을 탐색한다.
하지만 벨만 포드 알고리즘은 “한 번이라도 방문한 모든 정점” 을 탐색하며 최단거리를 계산한다.
따라서 시간복잡도가 O(ElogV)인 다익스트라 알고리즘 보다는 더 큰 시간복잡도를 갖게 되는데,
모든 간선을 정점의 개수 - 1회 만큼 탐색을 해야하기 때문에 O(VE)의 시간복잡도를 갖는다.

지금부터 기본 원리를 그림과 함께 이해해보자.
_진짜벨만포드 drawio

위와 같은 Directed graph가 있다고 생각해보자.
위의 그래프에서 1번 정점으로 부터 다른 모든 정점까지의 최단 경로를 어떻게 계산할 수 있을까?
최초의 Distance vector은 아래와 같이 갱신될 것이다.

distance vector drawio

Iteration 1

첫 간선 탐색에서는, 아래와 같은 순서로 갱신될 것이다.

  • 1 -> 2로 가는 거리를 3으로 갱신한다.
    • 이 때, 정점 2는 한 번이라도 방문한 정점이 된다!
  • 1 -> 3로 가는 거리를 2로 갱신한다.
    • 이 때, 정점 3은 한 번이라도 방문한 정점이 된다!
  • 1 -> 4로 가는 거리를 5로 갱신한다.
    • 이 때, 정점 4는 한 번이라도 방문한 정점이 된다!
  • 2 -> 3으로 가는 거리를 갱신해야 할 차례다.
    • 정점 2는 방문을 한 적이 있으므로 갱신 대상이 맞다.
    • 하지만, 기존의 dist[3]이 더 가까우므로 갱신을 하지 않는다!
  • 3 -> 4로 가는 거리를 갱신해야 할 차례다.
    • 정점 3은 방문을 한 적이 있으므로 갱신 대상이 맞다.
    • 기존의 dist[4]가 거리가 5인데, 1 -> 3 -> 4는 -2가 된다.
    • 따라서 이 경우는 거리를 새로 갱신해준다!
  • 4 -> 2로 가는 거리를 갱신해야 할 차례다.
    • 정점 4는 방문을 한 적이 있으므로 갱신 대상이 맞다.
    • 기존의 dist[2]는 거리가 3인데, 1 -> 4 -> 2는 -6이 된다.
    • 왜? 위에서 발생한 갱신에 의해 dist[4]가 -2가 되었었다.
    • 따라서 이 경우에도 거리를 새로 갱신해주어야 한다!

결국 처음 갱신된 Distance vector는 아래와 같은 모습이 될 것이다.

거리벡터 drawio

Iteration 2

두 번째 탐색부터는 1회차와 동일한 방식으로 간선을 탐색하게 된다.
하지만 어떤 차이가 있길래 반복 탐색을 하는 것일까?

1회차 탐색 시에는 한 번이라도 방문한 정점 이 탐색이 진행되며 생겨났다.
하지만 2회차 부터는 이미 방문한 상태가 된 정점의 수가 늘어난다.
따라서, 갱신 대상이 되는 정점의 수도 늘어 최단 거리의 갱신 여지가 더 생기는 것이다.

2회차 탐색의 결과 Distance vector는 아래와 같다.

2차거리벡터 drawio

주요 원인이 되었던 갱신은 아래와 같다.

  • 2 -> 3 으로 가는 간선에서 갱신이 발생한다.
    • 기존의 정점 2가 -6으로 갱신되었으므로, -6 + 3 = -3으로 갱신된다.
  • 3 -> 4로 가는 간선에서 갱신이 발생한다.
    • 기존의 정점 3이 위에서 -3이 되었으므로, -3 + (-4) = -7으로 갱신된다.
  • 4 -> 2로 가는 간선에서 갱신이 발생한다.
    • 기존의 정점 4이 위에서 -7이 되었으므로, -7 + (-4) = -11으로 갱신된다.

해당 예시에서는 더 이상 갱신은 발생하지 않지만 끝까지 갱신을 진행하도록 한다.

Negative Cycle?

그런데 정점의 개수 - 1회 만큼의 갱신이 끝났는데도 계속 갱신이 된다면?
그것은 분명히 문제가 있다는 뜻이며, 음의 사이클이 발생했다고 간주한다.

아래의 예시를 보도록 하자.
음의사이클 drawio

위의 경우에 각각의 정점 2 3 4의 갱신 과정을 간단히 생각해보면?

  • 최초에 1 3 -1로 갱신이 발생한다.
  • 2회차에서 0 2 -2으로 갱신된다.
  • 3회차에서 -1 1 -3으로 갱신된다.

위와 같은 모습을 보았을 때, 정점의 개수 - 1회가 지나도 계속 갱신이 될 것을 알 수 있다.
이는 사이클이 발생했을 때, 간선 가중치의 합이 음수이기 떄문에 발생하는 문제이다.
알고리즘 상에서 모든 탐색이 종료된 후 한 번더 탐색을 함으로써 음의 사이클을 발견해낼 수 있다.

Example : 백준 11657 - 타임머신

아래는 벨만 포드 알고리즘으로 문제를 푸는 코드의 예시이다.

public static void bellmanFord(long[] dist, ArrayList<Tuple> edges, int vertex) {
        for(int i = 0; i <= vertex - 1; i++){
            for(int j = 0; j < edges.size(); j++){
                int from = edges.get(j).from;
                int to = edges.get(j).to;
                long cost = edges.get(j).cost;

                if(dist[from] == Long.MAX_VALUE)
                    continue;
                // 갱신되지 않은 정점은 계산에 포함하지 않는다.
                if(dist[to] > dist[from] + cost)
                    dist[to] = dist[from] + cost;
                // 현재 저장된 거리보다 새로 이은 길의 거리가 더 짧으면?
                // 거리를 갱신한다.
            }
        }
    }