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

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

벨만-포드 알고리즘은 한 정점에서 다른 정점까지의 최단 거리를 구하는 알고리즘이다.

 

특징

벨만-포드 알고리즘의 시간 복잡도는 O(VE)로, O((V+E)logV)인 다익스트라보다 시간 복잡도가 더 크지만, 다익스트라는 가중치가 음수인 경우에는 사용할 수 없다.

반면, 벨만-포드 알고리즘은 가중치가 음수인 경우에도 사용할 수 있기 때문에 음수인 가중치가 존재한다면 벨만-포드 알고리즘을 사용할 필요가 있다.

 

구현

P[A][B]는 A와 B사이의 거리라고 가정한다.

1. 출발점으로부터 최단거리를 저장할 배열 d[v]를 만들고, 출발 노드에는 0을, 출발점을 제외한 다른 노드들에는 매우 큰 값 INF를 채워 넣는다. 실무에서는 보통 d의 원소 타입에 대한 최대값으로 설정한다.
2. 모든 간선에 대해, d[A] + P[A][B]와 d[B]의 값을 비교한다. INF와 비교할 경우 무조건 전자가 작다.
3. 만약 d[A] + P[A][B]의 값이 더 작다면, 즉 더 짧은 경로라면, d[B]의 값을 이 값으로 갱신시킨다.
4. 3 ~ 5의 과정을 v-1번 반복한다.
   • 음수 사이클을 확인하고 싶다면 v번 반복하여 v번째 반복 시 갱신할 값이 있는지 체크한다.

 

다음 코드는 [Baekjoon] 11657: 타임머신을 기준으로 작성하였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Q11657 {

    private static int n;
    private static int m;
    private static List<int[]> edges;
    private static long[] weights;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        edges = new ArrayList<>();
        String[] nm = br.readLine().split(" ");
        n = Integer.parseInt(nm[0]);
        m = Integer.parseInt(nm[1]);
        weights = new long[n + 1];
        Arrays.fill(weights, Integer.MAX_VALUE);
        weights[1] = 0;

        for (int i = 0; i < m; i++) {
            String[] abc = br.readLine().split(" ");
            int a = Integer.parseInt(abc[0]);
            int b = Integer.parseInt(abc[1]);
            int c = Integer.parseInt(abc[2]);
            edges.add(new int[]{a, b, c});
        }

        for (int i = 1; i <= n; i++) {
            for (int[] edge : edges) {
                int startNode = edge[0];
                int nextNode = edge[1];
                int nextWeight = edge[2];

                if (weights[startNode] != Integer.MAX_VALUE && weights[nextNode] > weights[startNode] + nextWeight) {
                    weights[nextNode] = weights[startNode] + nextWeight;
                    if (i == n) {
                        System.out.println(-1);
                        return;
                    }
                }
            }
        }

        for (int i = 2; i <= n; i++) {
            if (weights[i] == Integer.MAX_VALUE) {
                sb.append(-1).append("\n");
                continue;
            }
            sb.append(weights[i]).append("\n");
        }

        System.out.print(sb);
    }
}