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

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

가중그래프에서 특정 하나의 노드에서 다른 모든 노드로의 최단 거리 정보를 알아내는 알고리즘이다. (단일 출발)

모든 경우의 수를 고려하기 때문에, 다익스트라 알고리즘보다 시간복잡도가 높다.

그렇지만 다익스트라 알고리즘과 달리 노드 간의 간선 가중치가 음수인 경우에도 사용할 수 있다.

 

알고리즘 동작 방식

• 매 단계(cycle)마다 모든 노드(vertex)를 방문한다.
• 하나의 노드를 방문할 때마다 이 노드와 인접한 다른 노드들을 확인하여, 최단 거리 테이블을 갱신한다. 
• 단계는 최단 거리 테이블이 더이상 업데이트되지 않을 때까지, 최대 V-1번 반복된다. (V: vertex, 노드의 수)
• 만일 V-1번의 단계를 거친 이후에도 최단 거리 테이블이 업데이트 된다면, 이는 음수 사이클이 존재하는 것으로, 최단 경로를 구할 수 없다.

🤔 음수 사이클이란?

위 그림과 같은 상황에서 A에서 C로 가는 최단 경로를 구해보자.
A > B > C 로 가면 0이다. 그렇지만 한 바퀴를 더 돈다면?
A > B > C > A > B > C 면 -1이다. 또 한 바퀴를 더 돌면? -2이다.
이렇게 사이클을 돌릴 수록 끝도 없이 비용이 작아질 수 있어 최단 경로를 구할 수가 없게 되는데, 이런 경우 음수 사이클이 존재한다고 한다.

 

🤔  Cycle을 최대 V-1번 반복하는 이유는 뭘까?

벨만-포드 알고리즘에서는, 하나의 노드로부터 다른 노드로 갈 수 있는 모든 경우의 수를 확인한 뒤 최단 경로 테이블을 확정한다.

 

이유 1. 하나의 노드로부터 다른 노드로 갈 수 있는 edge의 수(경우의 수)의 최댓값은 V-1

V개의 노드가 있을 때, 하나의 노드에서 다른 노드로 이동할 때 거칠 수 있는 edge 수의 최댓값은 V-1이다.

 

이해하기 쉽게 5개의 노드가 일렬로 연결된 경우를 생각해보자.

 

보다싶이 5개의 노드가 있을 때, 어떤 한 노드에서 다른 노드로 갈 경우 거칠 수 있는 edge의 최대 값은 5-1인 4이다.

 

이유 2. N번째 사이클에서는 출발지에서 N개의 간선을 거쳐 노드에 도달하는 경우의 최단 거리 값을 확정할 수 있다

벨만-포드 알고리즘의 첫 번째 사이클에서는 출발 노드에 직접 연결된 노드들까지의 최단 거리를 갱신한다.
두 번째 사이클에서는? 출발 노드에서 두 개의 간선을 거쳐 도달할 수 있는 노드들의 최단 거리를 갱신한다.
즉, 각 사이클은 출발지로부터 몇 개의 edge를 사용하는 경우의 수인가를 상징한다.

 

이런 식으로 매 사이클마다 +1개의 간선을 거쳐 노드에 도달하는 경우의 수를 확인하고, 최단 거리를 갱신한다.

그런데 위에서 확인하였다싶이 하나의 노드에서 다른 노드로 이동할 때 거칠 수 있는 간선은 최대가 V-1이므로, 사이클을 최대 V-1번 돌리면 최단 거리 테이블이 확정될 수 있는 것이다.

 

여기서 내가 헷갈렸던 것을 적어본다. 이게 이해가 안 가서 몇 시간을 쏟았다ㅠㅠ
구현된 코드들을 보면 첫 번째 사이클에서도 edge 1개 뿐만 아니라 그 이상을 사용해서 갈 수 있는 노드들의 최단 거리 테이블도 갱신되게 되는데, 어째서 edge 1개를 사용하여 갈 수 있는 노드들의 최단 거리만을 갱신한다고 설명하는거지? 라고 생각했다.
!! 그러나 이것은 어디까지나 사이클 반복의 최대 횟수를 결정하기 위한 설명이다 !!
이론적으로는, 첫 번째 사이클에서는 edge 1개 이상을 사용해서 갈 수 있는 노드들까지만 확인한 뒤 최단 거리 테이블을 갱신하고, 두 번째 사이클에서는 앞에서 갱신한 노드들과 인접한 노드들만을 확인해서 최단 거리 테이블을 갱신한다. 이런 식으로 사용하는 edge의 수를 하나하나씩 늘려가서 V-1번의 사이클을 모두 돌리면 최단 거리 테이블이 확정된다.
그렇지만 실제 구현에서는 매 사이클마다 모든 노드들을 확인하여서, 이론 상으로 두 번째 사이클에서 수행될 작업을 첫 번째 사이클에서도 수행하게 된다. 따라서 반드시 V-1번의 사이클을 돌릴 필요가 없게 되며, 최대 V-1번을 돌리면 된다!!

 

구현 방법

1. 출발 노드(s) 설정
2. 최단 거리 테이블(D) 초기화
   1. D[s] = 0
   2. D[v] = ∞ (v는 출발 노드 s가 아닌 모든 vertex)
3. 탐색 사이클을 V-1번 실행한다.
   1. 매 사이클마다 모든 노드를 한 번씩 방문한다. 이 노드를 거쳐 다른 노드로 가는 거리를 계산하여 최단 거리 테이블을 갱신한다. (v와 연결된 각 노드 u에 대해, dist[u]과 dist[v] + 'v에서 u으로 가는 비용'을 비교하여 후자가 더 작다면 테이블 갱신)
   2. 더 이상 최단 거리 테이블이 갱신되지 않는다면 탐색을 종료한다.
4. 탐색 사이클이 V-1번 모두 실행되었다면 V번째 사이클을 실행한다.
   1. 이 때 또 다시 테이블이 갱신된다면 음수 사이클이 존재한다는 의미로, 최단 거리 테이블을 확정할 수 없다는 의미가 된다.

 

예시 문제 & 구현 코드

 

 

출발지를 1번 노드로 해서 다른 노드들로의 최단 거리를 구하면 되는 문제이다.

만일 음수 사이클이 존재한다면 -1을, 해당 노드로 가는 경로가 없다면 역시 -1을 출력하는 문제.

 

package shortestpath;

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

public class Boj11657_타임머신 {
    static int N, M;
    static long[] dist;
    static ArrayList<ArrayList<Edge>> edgeList;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 도시의 개수
        M = Integer.parseInt(st.nextToken()); // 버스 노선의 개수
        dist = new long[N+1];
        Arrays.fill(dist, Integer.MAX_VALUE);

        edgeList = new ArrayList<>();
        for(int i=0; i<=N; i++) {
            edgeList.add(new ArrayList<>());
        }
        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int time = Integer.parseInt(st.nextToken());
            edgeList.get(from).add(new Edge(to, time));
        }
        
        StringBuilder sb = new StringBuilder();
        if(bellmanFord(1)) {
            sb.append("-1\n");
        } else {
            for(int i=2; i<=N; i++) {
                sb.append(dist[i]==Integer.MAX_VALUE? -1:dist[i]).append("\n");
            }
        }
        System.out.println(sb);
    }

    // 반환 : 시간을 무한히 오래 전으로 되돌릴 수 있는가?
    static boolean bellmanFord(int start) {
        dist[start] = 0; // 시작 노드의 거리는 0으로 설정
        boolean updated = false;

        for(int i=1; i<N; i++) {
            updated = false;
            for(int j=1; j<=N; j++) {
                // 노드 j와 연결된 모든 노드 확인
                if(dist[j]==Integer.MAX_VALUE) continue;
                for(Edge edge: edgeList.get(j)) {
                    if(dist[edge.end] > dist[j]+edge.weight) {
                        dist[edge.end] = dist[j] + edge.weight;
                        updated = true;
                    }
                }
            }
            if(!updated) break; // 더 이상 갱신이 없으면 일찍 종료
        }

        // 음수 사이클 유무 확인
        if(updated) {
            for(int i=1; i<=N; i++) {
                for(Edge edge: edgeList.get(i)) {
                    if (dist[edge.end] > dist[i] + edge.weight) {
                        return true; // 음수 사이클 존재
                    }
                }
            }
        }
        return false;
    }

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