벨만 포드 알고리즘, 그림으로 쉽게 이해하기

1. 벨만포드 알고리즘이란?

음수인 가중치가 존재하는 그래프에서도 최단 경로를 구할 수 있게 해주는 알고리즘.

• 1️⃣ ONE TO ALL 알고리즘: 시작점을 고르면, 해당 정점에서 모든 정점까지의 최단 경로를 구할 수 있다.
• 2️⃣ 음수 가중치가 있어도 괜찮아: 다익스트라는 안되지?
• 3️⃣ 음수 사이클이 존재하는지도 확인 가능: 음수 사이클이 존재한다면, 사실 하나 이상의 정점으로의 최단 경로가 $- \infty $가 되기 때문에, 최단경로를 구하는 게 무의미해짐. 따라서 최단 경로를 구하는 게 무의미한지 여부도 파악 가능!

음수 사이클

가중치 그래프에서 정점 A에서 시작해서 A로 돌아왔는데 가중치의 합이 음수인 경우, 해당 사이클을 음수 사이클이라고 한다.

해당 예시에서는 사이클을 돌수록 출발지에서 A,B,C까지의 거리가 짧아진다. 따라서 최단경로를 구하는 것의 의미가 없다.

2. 벨만포드의 과정

정점의 수를 V, 간선의 수를 E라고 하자.

• 0️⃣ 사전 세팅
  • 시작 정점 정하기
  • 최단 거리 배열(이하 dist) 만들기 (index = 도착정점, value = 시작 정점에서 해당 정점까지의 최단 거리)
  • 그래프를 간선리스트로 구현하기 <출발 정점, 도착 정점, 간선 가중치>
• 1️⃣ $V-1$ 번 돌면서, 모든 간선에 대하여 다음을 반복한다.
  • 현재 보고 있는 간선의 정보를 <start=A, end=B, weight=C>라고 해보자.
  • 만약 dist[A] = $ \infty$ 이면 바로 다른 간선으로 넘어간다.
  • dist[A] $\neq \infty$ 일 시, dists[B] > dist[A] + C를 성립한다면, dist[B]를 dist[A] + C로 갱신한다. (이 갱신 과정을 완화라고 부른다.)
• 2️⃣ 마지막으로 한 번 더 1️⃣을 수행해본다. 이후 간선의 가중치가 더 작아진 녀석이 하나라도 존재하면, 해당 그래프에는 음수 사이클이 존재한다는 의미이다.

(1) 1️⃣을 V-1번만 반복하는 이유

정점의 수를 V개라 할 때, 임의의 정점 A에서 B로 가는 경로에서 존재할 수 있는 간선의 최대 개수는 V-1개 이다. 벨만포드 알고리즘은 1️⃣ 의 반복을 시행할 때마다, 간선을 하나씩 더 활용하며, 정점 사이의 비용을 완화한다. 따라서 V-1번의 계산 반복만 유의미한 가중치 완화를 일으킨다. V번째 부터는 음수 사이클이 있지 않는 한, 가중치 갱신이 되지 않는다.

(2) 그림으로 이해하기✨

벨만포드는 한번의 반복마다, 간선이 점진적으로 사용되며, 완화되는 과정을 보는 것이 중요한데, 그림으로 하나하나 그리기가 귀찮아서 생략하겠다. 해당 그림을 정말 잘 표현하신 블로그를 동봉드리니, 독자분들은 한 번보고 오시길 바란다.

 

[Algorithm] 벨만-포드 (Bellman-Ford) 알고리즘

 

3. 벨만포드의 구현

시작 정점이 모인 배열을 a[], 도착 정점이 모인 배열을 b [], 간선이 모인 배열을 c []라고 할 때, i 번째 값들은 하나의 간선을 나타낸다고 하자. 즉 a[i],b[i],c[i]는 a[i]에서 b[i]로 가는 가중치가 c[i]인 간선이다.

간선의 개수를 M개라고 할 때,

public class Main {    
    static int [] a, b;
    static long [ ] c, dist;
    public static void main(String[] args) throws IOException { 
        for (int i = 0; i < M; i++) {
            int start   = a[i];
            int end     = b[i];
            long weight  = c[i];
            long oldValue = dist[end];

            if(dist[start] != Long.MAX_VALUE){
                dist[end] = Math.min(dist[end], dist[start] + weight);
            }

            if(oldValue != dist[end]){
                System.out.println(-1);
                return;
            }
        }
    }
}

M-1번째 반복까지는 dist[]의 값을 계속 완화시켜 작게 갱신한다. 이후 M번째 반복에서는 하나의 최단 거리 값이라도, 완화 과정을 거쳤더니, 값이 갱신되면 음수 사이클이 있는 것임으로, 해당 그래프는 최단 거리 계산이 불가하다는 의미의 -1을 출력했다.