(알고리즘/Java) 벨만-포드 (Bellman-Ford) 알고리즘

 

1. 개념

그래프의 최단 경로를 구하는 알고리즘으로 벨만-포드 외에도 그래프의 다익스트라(Dijkstra)와 플로이드-와샬(Floyd-Wrasahll)이 있으며 이전 포스팅을 통해 다뤘었다.

벨만-포드 알고리즘은 다음과 같은 특성을 가진다.

• 그래프의 최단 경로를 구하는 알고리즘
• 하나의 정점에서 출발하는 최단거리를 구함
• 음수 가중치는 허용하되, 음수 사이클이 없어야 함
• O(nm)의 시간복잡도
• 동적 계획법 사용

하나의 출발지를 지정해 최단거리를 구한다는 측면에서 다익스트라와 같지만 음수가중치를 허용한다는 점에서 다익스트라와 차이가 있다.

 

2. 알고리즘 단계

 

알고리즘 과정

벨만-포드 알고리즘의 과정에 대해 단계별로 살펴보자.

다익스트라와 마찬가지로 dist배열을 통해 최단거리를 기록할 것이다.

N개의 노드가 있을 때, N-1번만큼 아래 2,3번 과정을 반복한다.

 

1) 출발지는 0, 나머지는 INF로 초기화하여 시작한다.

 

2) 간선 m개를 모두 살펴본다. 

v에서 출발하여 w에 도착하는 간선을 살펴볼 때, dist[w]가 INF가 아니라면 dist[w]의 갱신을 시도한다.

 

3) dist[w] = min( dist[v] + cost(v,w), dist[w] ) 으로 갱신한다. 

즉, v까지 가는 길이 무한대가 아니었다면 v까지 도착한 후, v에서 w까지 가는 비용과 (v를 거쳐 w로 오는 비용) 지금까지 알아낸 w까지 오는 최소 비용을 비교하여 더 작은 값으로 최소비용을 갱신하는 것이다.

 

 

음수 사이클 확인하기

벨만-포드는 다익스트라와 다르게 음수 사이클이 존재하는 지에 대해 주의할 필요가 있다. 음수 가중치를 허용하기 때문이다. 

출발 노드에서부터 다른 노드까지 dist를 모두 갱신한 후에 한번 더 dist를 점검하며 한 번이라도 더 갱신되는 값이 있을 경우, 계속 음수로 줄어들게 만드는 음수사이클이 존재한다는 의미이다. 따라서 위 알고리즘과정의 2,3번을 N-1번이 아닌 N번 반복하여 N번째 반복에서 dist가 갱신되는 경우가 존재하는지를 판별하면 된다.

 

 

3. 구현 코드

아래는 벨만 포드를 활용해 해결한 백준 11657번 타임머신의 답안이다. 

간선리스트를 활용하였으며 시작지점으로부터의 최소거리를 dist배열로 관리하다가 한번 더 for문이 돌았을 때 dist가 갱신되면 음수사이클이 존재함을 구현하였다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.sql.SQLOutput;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main {


    static int N;
    static int M;

    static long[] dist;
    static List<Edge> edges;

    static final int INF = 1000000000;

    public 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;
        }
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        edges = new ArrayList<>();
        dist = new long[N + 1];
        int inf = Integer.MAX_VALUE;
        Arrays.fill(dist, inf);



        for (int m = 0; m < M; m++) {
            st = new StringTokenizer(br.readLine());

            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            edges.add(new Edge(start, end, cost));
        }


        boolean result = bellman(1);


        if (result) sb.append(-1);
        else {
            for (int i = 2; i <= N; i++) {
                if (dist[i] != INF) sb.append(dist[i]).append("\n");
                else sb.append(-1).append("\n");
            }
        }
        System.out.println(sb.toString());
    }

    public static boolean bellman(int start) {

        Arrays.fill(dist, INF);

        dist[start] = 0;

        for (int k = 1; k <= N; k++) {

            for(Edge edge : edges){
                if (dist[edge.start] !=INF && dist[edge.end] > dist[edge.start] + edge.cost) {
                    dist[edge.end] = dist[edge.start] + edge.cost;
                    if (k == N) {
                        return true; //음수사이클 존재
                    }
                }

            }
        }


        return false;


    }


}