Bellman-Ford

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

 

벨만-포드 알고리즘은 최단 경로를 구하는 알고리즘으로, 특히 음의 가중치를 갖는 간선이 있는 그래프에서도 동작하는 알고리즘입니다. 다익스트라 알고리즘과 달리 음의 가중치를 처리할 수 있다는 점에서 중요한 특성을 가집니다.

 

기본 아이디어
벨만-포드 알고리즘은 그리디 방식이 아닌 동적 계획법(DP)을 기반으로 하는 알고리즘입니다. 각 단계에서 모든 간선을 한번씩 탐색하면서, 각 노드의 최단 거리를 점차적으로 갱신합니다.

 

알고리즘 동작 원리
1. 초기화:
   - 시작 노드의 거리는 0, 나머지 노드들은 무한대(`INFINITY`)로 설정합니다.
  
2. 간선 완화(Relaxation):
   - 그래프의 모든 간선 `(u, v)`에 대해, `dist[u] + weight(u, v) < dist[v]`이면, `dist[v]`를 `dist[u] + weight(u, v)`로 갱신합니다.
   - 이 과정을 모든 간선에 대해 `V - 1`번 반복합니다. 여기서 `V`는 노드의 개수입니다. (`V - 1`번 반복하는 이유는, 최단 경로에서 최대 `V-1`개의 간선만 사용할 수 있기 때문입니다.)

3. 음의 가중치 사이클 검출:
   - `V - 1`번의 반복 이후에도 거리가 갱신될 수 있다면, 이는 음의 가중치 사이클이 존재한다는 것을 의미합니다.

 

알고리즘의 단계
1. 초기화: 출발 노드의 거리는 0, 나머지 노드의 거리는 무한대로 설정.
2. Relaxation: 모든 간선에 대해 `V - 1`번 반복하여 최단 거리 갱신.
3. 사이클 검출: `V - 1`번의 반복 후, 여전히 거리가 갱신되는 간선이 있으면 음의 가중치 사이클이 존재한다고 판단.

 

벨만-포드 알고리즘의 구현

import java.util.;

class BellmanFord {
    private static final int INF = Integer.MAX_VALUE;

    // 벨만-포드 알고리즘
    public boolean bellmanFord(int n, int start, int[][] edges, int[] dist) {
        // 초기화: 출발 노드의 거리는 0, 나머지는 무한대로 설정
        Arrays.fill(dist, INF);
        dist[start] = 0;

        // V-1 번 반복 (최단 경로가 최대 V-1개의 간선만으로 이루어지기 때문)
        for (int i = 1; i < n; i++) {
            // 모든 간선에 대해 완화 연산 수행
            for (int[] edge : edges) {
                int u = edge[0], v = edge[1], weight = edge[2];
                if (dist[u] != INF && dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                }
            }
        }

        // 음의 가중치 사이클 검출
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], weight = edge[2];
            if (dist[u] != INF && dist[u] + weight < dist[v]) {
                return false;  // 음의 사이클 존재
            }
        }

        return true;  // 음의 사이클이 없으면 정상적으로 종료
    }

    public static void main(String[] args) {
        BellmanFord bf = new BellmanFord();
        
        int n = 5; // 노드의 수
        int start = 0; // 출발 노드 (0번)
        
        // 간선 정보 (u, v, weight) 형태로 입력
        int[][] edges = {
            {0, 1, -1}, // 0 -> 1 (가중치 -1)
            {0, 2, 4},  // 0 -> 2 (가중치 4)
            {1, 2, 3},  // 1 -> 2 (가중치 3)
            {1, 3, 2},  // 1 -> 3 (가중치 2)
            {1, 4, 2},  // 1 -> 4 (가중치 2)
            {3, 2, 5},  // 3 -> 2 (가중치 5)
            {3, 1, 1},  // 3 -> 1 (가중치 1)
            {4, 3, -3}  // 4 -> 3 (가중치 -3)
        };
        
        int[] dist = new int[n];  // 최단 거리 배열

        boolean hasNegativeCycle = !bf.bellmanFord(n, start, edges, dist);

        if (hasNegativeCycle) {
            System.out.println("그래프에 음의 가중치 사이클이 존재합니다.");
        } else {
            System.out.println("최단 거리:");
            for (int i = 0; i < n; i++) {
                if (dist[i] == INF) {
                    System.out.println(i + " : 도달 불가");
                } else {
                    System.out.println(i + " : " + dist[i]);
                }
            }
        }
    }
}

설명
1. `bellmanFord` 메서드:
   - 입력: `n` (노드의 개수), `start` (출발 노드), `edges` (간선 정보: 각 간선은 `{출발 노드, 도착 노드, 가중치}`), `dist` (최단 거리 배열)
   - 동작: 출발 노드에서 모든 다른 노드로 가는 최단 거리를 계산합니다. 이를 위해 `V - 1`번의 반복을 통해 모든 간선에 대해 "완화(Relaxation)" 연산을 수행하고, 마지막으로 음의 가중치 사이클이 있는지 확인합니다.
   - 출력: 음의 가중치 사이클이 발견되면 `false`를 반환하고, 그렇지 않으면 `true`를 반환합니다.

2. 간선 완화(Relaxation):
   - 각 간선 `(u, v)`에 대해 `dist[u] + weight < dist[v]`이면, `dist[v]`를 갱신합니다.

3. 사이클 검출:
   - `V - 1`번의 반복 후, 여전히 `dist[u] + weight < dist[v]`가 성립되는 간선이 있다면, 음의 가중치 사이클이 존재하는 것입니다.

 

시간 복잡도
벨만-포드 알고리즘의 시간 복잡도는 O(E * V)입니다. 여기서 `E`는 간선의 수, `V`는 노드의 수입니다.

- 각 간선을 `V - 1`번 반복하면서 탐색하므로, 총 `V - 1`번의 반복을 통해 모든 간선에 대해 완화 작업을 수행합니다.
- 따라서 시간 복잡도는 O(V  E)입니다.

 

벨만-포드 알고리즘의 장점
1. 음의 가중치 처리 가능: 벨만-포드는 음의 가중치를 가진 간선이 포함된 그래프에서도 작동하며, 음의 가중치 사이클을 감지할 수 있습니다.
2. 단순성: 구현이 비교적 간단하고, 다익스트라처럼 우선순위 큐를 사용할 필요가 없습니다. (참고: 다익스트라 알고리즘)

 

벨만-포드 알고리즘의 단점
1. 시간 복잡도: 시간 복잡도가 O(V * E)로, 다익스트라 알고리즘에 비해 느립니다. 특히, 그래프가 매우 크면 성능 저하가 발생할 수 있습니다.
2. 우선순위 큐 사용 불가: 벨만-포드는 그리디 알고리즘을 사용하지 않으므로, 다익스트라처럼 우선순위 큐를 이용한 최적화가 불가능합니다.