Bellman-Ford 알고리즘

흔히 그래프에서 최단 거리를 구하는 알고리즘은 다익스트라를 떠올리기 쉽다. 하지만 다익스트라는 음수 가중치가 있는 경우에는 사용이 불가능하다.

 

다익스트라에 대한 자세한 설명과 과정들은 다음 링크에서 볼 수 있다.

다익스트라, Dijkstra Algorithm

 

그럼 음수 가중치가 있는 그래프에 다익스트라를 적용하면 어떻게 되는지 한 번 해보자.

 

음수 가중치에 다익스트라?

다음 예시를 보자.

위 그래프에 다익스트라를 적용해보자. 시작점을 1로 하여 다른 모든 노드로의 최단 거리를 다익스트라를 활용해 구해보자.

시간/노드 번호	1	2	3	4	PQ (방문할 노드, 비용)
0	0	무한	무한	무한	(2, 1)
1	0	1	무한	무한	(3, 2)
2	0	1	2	무한	(4, 4)
3	0	1	2	4	-

 

노드 4에서 2로 가는 가중치가 -5인 간선이 있지만, 노드 2는 이미 방문했기 때문에 이를 고려하지 않게 된다. 사실 다익스트라 알고리즘은 모든 가중치가 ‘양수’라는 가정이 있기 때문에 이가 가능하다. 이미 방문한 노드에 대해서 한 번 더 방문한다는 것은, 양의 가중치만 있다면 무조건 비용이 더 커지기 때문에 끊어버린 것이다.

 

하지만 이 상황처럼 음의 가중치가 존재한다면, 해당 간선을 통해 가는 게 비용적으로는 훨씬 이득이다. 즉, 다익스트라의 결과로 나온 1→2의 최단 경로는 1이지만, 실제로는 마이너스 무한대가 된다.

 

이러한 다익스트라의 문제를 해결하기 위해 나온 것이 밸만 포드 알고리즘이다.

Bellman-Ford, 밸만 포드 알고리즘

🔎 Bellman-Ford, 밸만 포드

한 노드에서 다른 모든 노드까지의 최단거리를 구하는 일고리즘으로, 다익스트라와 달리 가중치에 음수가 있어도 사용이 가능하다.
시간 복잡도 : O(NE) (N : 노드의 수, E : 엣지의 수)

 

알고리즘 동작 과정

1. 출발 노드를 설정한다.
2. 최단 거리 테이블을 초기화한다 (dist[] : 무한대로 초기화)
3. 다음의 과정을 N-1번 반복한다.
   1. 전체 간선 E개를 하나씩 확인한다
   2. 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여, 최단 거리 테이블을 갱신한다.
   이 결과로 나온 값이 최단 거리이다.
4. 하지만 여기서 음수 간선의 순환이 발생하는지 체크하고 싶다면, 3번 과정을 한 번 더 수행한다.
   1. 만약 최단 거리 테이블이 갱신된다면, 음수 간선 순환이 존재하는 것이다. 음수 간선 순환은 돌면 돌수록 값이 작아지기 때문이다.

🔎 음수 순환 간선이란, 간선의 비용이 음수일 경우 해당 간선을 계속 지나가면 이어진 다른 노드로 가는 비용이 무한대로 작아지는 경우를 말한다.

 

코드

다음 문제를 하나 풀어보면서 필요한 자료구조를 정리해보자

11657번: 타임머신

 

필요한 자료구조는 다음과 같이 두 개이다.

 

1. Edge를 저장한 배열 - (시작, 끝, 비용) 정보를 담는 class 배열

static class Edge {
        int start;
        int end;
        int cost;
        public Edge(int start, int end, int cost){
            this.start = start;
            this.end = end;
            this.cost = cost;
        }
}

 

2. dist를 저장하는 배열 - N * M * cost 크기에 따라 자료형 결정

static long[] dist;

 

현재 문제에는 500 * 6000 * 10000이므로 long으로 결정!

 

위 두 개의 자료구조를 활용해 문제를 해결하면 다음과 같이 해결할 수 있다.

package ps.ㄱSolving;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class BOJ_G4_11657_타임머신 {
    static class Edge {
        int start;
        int end;
        int cost;
        public Edge(int start, int end, int cost){
            this.start = start;
            this.end = end;
            this.cost = cost;
        }
    }
    static int N, M;
    static List<Edge> graph;
    static long[] dist;
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        //음수 순환되면 첫째줄에 -1
        //아니면 N개의 줄에 각각 도시로 가는 시간을 순서대로 출력. 해당 도시로 가는 경로가 없다면 -1 출력.

        StringTokenizer st = new StringTokenizer(in.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        graph = new ArrayList<>();
        for (int i = 0; i < M ;i++){
            st = new StringTokenizer(in.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            graph.add(new Edge(start, end, cost));
        }

        //밸만포드
        dist = new long[N+1];
        Arrays.fill(dist, INF);
        dist[1] = 0;
        if (bellmanFord()){
            System.out.println(-1);
        }
        else{
            StringBuilder sb = new StringBuilder();
            for (int i = 2; i < N+1; i++){
                sb.append((dist[i] == INF)? -1 : dist[i]).append("\\n");
            }
            System.out.println(sb);
        }
    }
    static Long INF = Long.MAX_VALUE - 10001;

    private static boolean bellmanFord() {
        //N-1번 반복
        for (int i = 0; i < N-1; i++){
            //모든 간선을 다 보면서 dist 업데이트
            for (Edge e : graph){
                if (dist[e.start] == INF) continue;
                if (dist[e.end] > dist[e.start] + e.cost){
                    dist[e.end] = dist[e.start] + e.cost;
                }
            }
        }

        //한 번 반복해서 순환하는지
        boolean isCycle = false;
        for (Edge e : graph){
            if (dist[e.start] == INF) continue;

            if (dist[e.end] > dist[e.start] + e.cost){
                isCycle = true;
            }
        }
        return isCycle;
    }
}

다익스트라와 다른 점

• Edge를 (시작점, 끝점, 비용) 형태로 입력 받고, 하나의 배열에 다 저장한다
• 해당 배열을 계속 반복 순회하면서 비용을 갱신한다
• 음수 순환이 될 수도 있다. 해당 경우에는 최단 거리가 무한대로 작아진다.

---

참고자료

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

 

[알고리즘/ 그래프] 벨만 포드 알고리즘 (Bellman-Ford Algorithm) (Java)