최단 경로 알고리즘 (2): 벨만-포드 알고리즘 (Bellman-Ford Algorithm)

1. 벨만-포드 알고리즘이란?

벨만-포드 알고리즘(Bellman-Ford Algorithm)은 가중치 그래프에서 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다. 다익스트라 알고리즘과 유사하지만, 음수 가중치를 포함한 그래프에서도 동작한다.

이 알고리즘은 그래프의 모든 간선을 여러 번 확인하며 최단 경로를 반복적으로 갱신하는 방식으로 동작한다. 특히 음수 가중치를 처리할 수 있으며, **음수 사이클(Negative Cycle)**이 있는지도 판별할 수 있다.

1.1 벨만-포드 알고리즘의 특징

• 음수 가중치 허용: 음수 가중치를 포함한 그래프에서 사용 가능
• 음수 사이클 탐지: 음수 가중치의 무한 루프 발생 여부 확인 가능
• 시간 복잡도: O(V × E) (V는 정점 수, E는 간선 수)

2. 벨만-포드 알고리즘의 동작 원리

벨만-포드 알고리즘은 다음과 같은 절차로 수행된다:

1. 초기화:
   • 출발 노드의 거리를 0으로 설정하고, 나머지 노드는 무한대로 초기화
2. 거리 갱신:
   • 모든 간선을 (V-1)번 반복하며 각 간선을 확인
   • 새로운 경로가 더 짧으면 해당 경로로 업데이트
3. 음수 사이클 확인:
   • V번째 반복에서 더 짧은 경로가 발견되면 음수 사이클 존재

2.1 벨만-포드 알고리즘 예제

다음과 같은 가중치 그래프가 주어졌을 때, 노드 0에서 시작해 각 노드까지의 최단 경로를 구한다.

     (0)
   /  | 
  4   2
  |   |  
 (1) (2) (3)
  |   |   |
  6  -3   3
   \  |  /
     (4)

2.2 벨만-포드 알고리즘의 수행 과정

1. 출발 노드(0)의 거리를 0으로, 나머지 노드는 ∞로 초기화
2. 모든 간선을 (V-1)번 반복하며 거리 갱신
3. 추가로 한 번 더 확인해 음수 사이클 여부 검사

3. 벨만-포드 알고리즘 구현 (Java)

import java.util.*;

class Edge {
    int src, dest, weight;

    Edge(int src, int dest, int weight) {
        this.src = src;
        this.dest = dest;
        this.weight = weight;
    }
}

public class BellmanFord {

    public static void bellmanFord(List<Edge> edges, int V, int start) {
        int[] distance = new int[V];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[start] = 0;

        // (V - 1)번 반복하여 거리 갱신
        for (int i = 0; i < V - 1; i++) {
            for (Edge edge : edges) {
                if (distance[edge.src] != Integer.MAX_VALUE && distance[edge.src] + edge.weight < distance[edge.dest]) {
                    distance[edge.dest] = distance[edge.src] + edge.weight;
                }
            }
        }

        // 음수 사이클 검사
        for (Edge edge : edges) {
            if (distance[edge.src] != Integer.MAX_VALUE && distance[edge.src] + edge.weight < distance[edge.dest]) {
                System.out.println("음수 사이클이 존재합니다.");
                return;
            }
        }

        // 결과 출력
        for (int i = 0; i < V; i++) {
            System.out.println("노드 " + i + "까지의 최단 거리: " + distance[i]);
        }
    }

    public static void main(String[] args) {
        int V = 5; // 정점 수
        List<Edge> edges = new ArrayList<>();

        edges.add(new Edge(0, 1, 4));
        edges.add(new Edge(0, 2, 2));
        edges.add(new Edge(1, 4, 6));
        edges.add(new Edge(2, 4, -3));
        edges.add(new Edge(3, 4, 3));

        bellmanFord(edges, V, 0);
    }
}

4. 벨만-포드 알고리즘의 성능 분석

4.1 시간 복잡도

• O(V × E): 모든 간선을 V-1번 확인

4.2 공간 복잡도

• O(V): 거리 정보를 저장하는 배열

5. 벨만-포드 알고리즘의 장점과 단점

5.1 장점

• 음수 가중치가 있는 그래프에서 사용 가능
• 음수 사이클 여부 판별 가능
• 구현이 간단하고 직관적

5.2 단점

• 시간 복잡도가 O(V × E)로 크기 때문에 큰 그래프에서 비효율적
• 음수 사이클이 있을 경우 경로 계산 불가

6. 벨만-포드 알고리즘의 활용 사례

• 금융 분야: 손익 계산, 주가 변동 분석
• 네트워크 라우팅: 라우터 간의 최단 경로 탐색
• 도로망 분석: 음수 비용 경로를 포함한 교통망 분석

7. 벨만-포드 알고리즘 vs. 다익스트라 알고리즘

특징벨만-포드 알고리즘다익스트라 알고리즘

시간 복잡도	O(V × E)	O((V + E) log V)
음수 가중치 허용	✅ 허용	❌ 허용하지 않음
구현 복잡도	쉬움	다소 복잡함
음수 사이클 탐지	✅ 탐지 가능	❌ 탐지 불가능
적용 분야	음수 비용 존재 시 유용	양수 가중치 그래프 최단 경로

8. 결론

벨만-포드 알고리즘은 음수 가중치와 음수 사이클을 처리할 수 있는 강력한 최단 경로 알고리즘으로, 음수 가중치가 없는 경우에는 다익스트라 알고리즘이 더 효율적이다. 주어진 문제의 특성에 따라 적합한 알고리즘을 선택하는 것이 중요하다.