6-5. 그래프: 최단 경로 (Bellman-Ford)

1. 벨만-포드 알고리즘 소개

최단 경로 문제는 그래프 이론에서 매우 중요한 문제 중 하나입니다. 그래프 내의 특정 노드(시작 노드)에서 다른 모든 노드까지의 최단 경로를 찾는 알고리즘은 다양한 분야에서 활용됩니다. 예를 들어, 네비게이션 시스템에서 최단 경로를 계산하거나, 네트워크 라우팅 프로토콜에서 효율적인 데이터 전송 경로를 결정하는 데 사용됩니다. 지금까지 Dijkstra 알고리즘을 살펴보았습니다. Dijkstra 알고리즘은 가중치가 음수가 아닌 경우에 효과적이지만, 음수 가중치가 있는 그래프에서는 제대로 동작하지 않는다는 단점이 있습니다. 이러한 문제를 해결하기 위해 등장한 알고리즘이 바로 Bellman-Ford 알고리즘입니다.

Bellman-Ford 알고리즘은 음수 가중치를 포함하는 그래프에서도 최단 경로를 계산할 수 있는 알고리즘입니다. 뿐만 아니라, 그래프 내에 음수 사이클이 존재하는지 여부를 감지할 수 있다는 장점도 가지고 있습니다. 음수 사이클이란, 그래프 내에서 가중치의 합이 음수가 되는 사이클을 의미하며, 이러한 사이클이 존재하면 최단 경로가 무한히 작아질 수 있기 때문에 최단 경로를 정의할 수 없습니다.

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

Bellman-Ford 알고리즘은 각 노드까지의 최단 거리를 반복적으로 갱신하는 방식으로 작동합니다. 알고리즘은 다음과 같은 단계를 거칩니다.

1. 초기화: 시작 노드에서 다른 모든 노드까지의 거리를 무한대(∞)로 초기화합니다. 시작 노드에서 자기 자신까지의 거리는 0으로 초기화합니다.

2. 반복: 모든 간선에 대해 다음과 같은 연산을 V - 1번 반복합니다. 여기서 V는 그래프 내 노드의 개수입니다.

   • 각 간선 (u, v)에 대해, u에서 v까지의 현재 거리를, u까지의 현재 거리 + 간선의 가중치와 비교합니다.
   • 만약 u까지의 현재 거리 + 간선의 가중치가 v까지의 현재 거리보다 작다면, v까지의 거리를 이 값으로 갱신합니다. 즉, dist[v] = min(dist[v], dist[u] + weight(u, v))

3. 음수 사이클 감지: V - 1번의 반복 이후, 다시 한번 모든 간선에 대해 위 2번 단계를 수행합니다. 만약 어떠한 노드의 거리라도 갱신된다면, 그래프 내에 음수 사이클이 존재한다는 것을 의미합니다.

1) 완화 (Relaxation)

Bellman-Ford 알고리즘의 핵심은 완화(Relaxation) 연산입니다. 완화는 각 간선을 통해 최단 거리를 갱신하는 과정을 의미합니다. 위에서 설명한 dist[v] = min(dist[v], dist[u] + weight(u, v)) 이 수식이 바로 완화 연산을 나타냅니다. 즉, 현재 u 노드까지의 최단 거리 dist[u]와 간선 (u, v)의 가중치 weight(u, v)를 더한 값이 v 노드까지의 현재 최단 거리 dist[v]보다 작다면, dist[v]를 갱신합니다. 이러한 완화 과정을 모든 간선에 대해 반복적으로 수행함으로써, 시작 노드로부터 다른 모든 노드까지의 최단 거리를 점진적으로 찾아나갈 수 있습니다.

2) 왜 V - 1번 반복하는가?

Bellman-Ford 알고리즘이 V - 1번 반복하는 이유는, 최악의 경우, 최단 경로가 최대 V - 1개의 간선을 거쳐서 도달할 수 있기 때문입니다. 예를 들어, 시작 노드에서 다른 모든 노드로 가는 경로가 순차적으로 연결된 경우를 생각해 볼 수 있습니다. 각 반복마다 하나의 간선이 고려되어 최단 거리가 갱신되므로, V - 1번의 반복을 통해 모든 노드까지의 최단 거리를 정확하게 계산할 수 있습니다.

3) 음수 사이클 감지 원리

Bellman-Ford 알고리즘은 V - 1번의 반복 이후에도 최단 거리가 갱신되는 경우, 음수 사이클이 존재한다고 판단합니다. 이는 음수 사이클을 순환하는 경로를 따라가면, 거리가 계속 감소하기 때문에 나타나는 현상입니다. 만약 음수 사이클이 존재한다면, 알고리즘은 무한히 반복될 것이고, 최단 거리는 계속해서 갱신될 것입니다. 따라서 V - 1번의 반복 이후에도 거리가 갱신된다는 것은 음수 사이클이 존재한다는 강력한 증거가 됩니다.

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

Bellman-Ford 알고리즘은 비교적 간단하게 구현할 수 있습니다. 아래는 파이썬으로 작성된 예시 코드입니다.

import sys

def bellman_ford(graph, source):
    """
    Bellman-Ford 알고리즘 구현

    Args:
        graph: 그래프 (딕셔너리 형태). 각 키는 노드, 값은 인접 노드와 가중치의 튜플 리스트
               예: {'A': [('B', 5), ('C', 2)], 'B': [('C', 1)]}
        source: 시작 노드

    Returns:
        각 노드까지의 최단 거리 (딕셔너리)와 음수 사이클 존재 여부 (boolean)
        만약 음수 사이클이 존재하면, None을 반환
    """
    nodes = list(graph.keys())
    dist = {node: float('inf') for node in nodes}
    dist[source] = 0

    # V - 1 번 반복
    for _ in range(len(nodes) - 1):
        for u in nodes:
            for v, weight in graph.get(u, []):
                if dist[u] != float('inf') and dist[u] + weight < dist[v]:
                    dist[v] = dist[u] + weight

    # 음수 사이클 감지
    for u in nodes:
        for v, weight in graph.get(u, []):
            if dist[u] != float('inf') and dist[u] + weight < dist[v]:
                return None, True # 음수 사이클 존재

    return dist, False # 최단 거리, 음수 사이클 없음

1) 코드 해설

• graph: 그래프는 딕셔너리 형태로 표현됩니다. 키는 노드를 나타내고, 값은 인접 노드와 가중치의 튜플 리스트입니다.
• source: 시작 노드를 지정합니다.
• 초기화: 모든 노드의 거리를 무한대(float('inf'))로 설정하고, 시작 노드의 거리는 0으로 설정합니다.
• V - 1번 반복: 모든 간선에 대해 완화 연산을 수행합니다.
• 음수 사이클 감지: V - 1번의 반복 이후, 다시 한 번 모든 간선에 대해 완화 연산을 수행하여, 만약 거리 갱신이 발생하면 음수 사이클이 존재함을 감지합니다.

2) 사용 예시

# 예시 그래프
graph = {
    'A': [('B', 5), ('C', 2)],
    'B': [('C', 1), ('D', 6)],
    'C': [('D', 3)],
    'D': []
}

source_node = 'A'
shortest_paths, has_negative_cycle = bellman_ford(graph, source_node)

if shortest_paths is None:
    print("음수 사이클이 존재합니다.")
else:
    print("최단 거리:", shortest_paths)
    if has_negative_cycle:
        print("경고: 음수 사이클이 존재하지만 최단 거리가 계산되었습니다.")

4. 벨만-포드 알고리즘의 시간 복잡도

Bellman-Ford 알고리즘의 시간 복잡도는 O(V * E)입니다. 여기서 V는 노드의 개수, E는 간선의 개수를 의미합니다. 알고리즘은 V - 1번의 반복을 수행하고, 각 반복마다 모든 간선에 대해 완화 연산을 수행하기 때문입니다. Dijkstra 알고리즘의 시간 복잡도(O(E log V))에 비해, 간선의 개수가 많은 그래프에서는 상대적으로 비효율적일 수 있습니다. 하지만 음수 가중치를 처리할 수 있다는 장점 때문에, 음수 가중치가 있는 그래프에서는 Bellman-Ford 알고리즘이 유일한 선택지가 될 수 있습니다.

5. 벨만-포드 알고리즘의 활용

Bellman-Ford 알고리즘은 다음과 같은 다양한 분야에서 활용될 수 있습니다.

• 네트워크 라우팅: 네트워크 라우팅 프로토콜, 특히 Distance Vector 라우팅 프로토콜에서 사용될 수 있습니다.
• GPS 시스템: GPS 시스템에서 최단 경로를 계산하는 데 활용될 수 있습니다.
• 자원 할당 문제: 자원 할당 문제에서 최적의 할당 방안을 찾는 데 사용될 수 있습니다.
• 통화 변환: 통화 간의 환율 정보를 이용하여, 주어진 통화에서 다른 통화로 변환할 때 최적의 환율 경로를 찾는 데 활용될 수 있습니다. 음수 사이클은 환율 차익 거래(arbitrage)를 의미하며, 이는 현실적으로 불가능합니다. 따라서 음수 사이클 감지를 통해 잘못된 환율 정보를 탐지할 수 있습니다.

6. 주의사항과 트러블슈팅

1) 음수 가중치와 음수 사이클

Bellman-Ford 알고리즘은 음수 가중치를 처리할 수 있지만, 그래프에 음수 사이클이 존재할 경우 최단 경로를 정의할 수 없으므로, 알고리즘이 올바르게 동작하지 않습니다. 음수 사이클이 존재하면, 알고리즘은 무한히 반복될 수 있으며, 최단 거리가 계속해서 갱신될 수 있습니다. 따라서 음수 사이클을 감지하는 것이 중요합니다.

2) 초기화 문제

시작 노드에서 도달할 수 없는 노드는 무한대(∞)로 초기화되어야 합니다. 이는 알고리즘이 올바르게 동작하기 위한 중요한 조건입니다.

3) 최적화

그래프가 희소 그래프인 경우, 모든 간선을 반복적으로 확인하는 것은 비효율적일 수 있습니다. 이러한 경우, Dijkstra 알고리즘과 같은 다른 알고리즘을 고려해 볼 수 있습니다. 또한, Bellman-Ford 알고리즘을 최적화하기 위해, 완화가 발생한 노드만을 큐에 넣고, 큐에서 노드를 꺼내 완화를 수행하는 방식을 사용할 수 있습니다. 이러한 최적화 기법을 SPFA(Shortest Path Faster Algorithm)라고 합니다. 하지만 SPFA는 최악의 경우 시간 복잡도가 O(V * E)가 될 수 있으며, 음수 사이클 감지의 정확성이 보장되지 않을 수 있다는 단점이 있습니다.

7. 결론

Bellman-Ford 알고리즘은 음수 가중치를 포함하는 그래프에서 최단 경로를 계산하고, 음수 사이클을 감지하는 강력한 알고리즘입니다. Dijkstra 알고리즘에 비해 시간 복잡도가 높지만, 음수 가중치를 처리할 수 있다는 장점 때문에 다양한 분야에서 활용됩니다. 알고리즘의 원리를 이해하고, 구현 방법을 숙지하면, 그래프 이론 문제 해결 능력을 향상시키는 데 도움이 될 것입니다.