벨만-포드 알고리즘 개요

벨만-포드 알고리즘은 그래프에서 한 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다. 다익스트라 알고리즘과 달리 음수 가중치를 가진 간선이 있는 경우에도 사용할 수 있다.

알고리즘의 특징

• 시간 복잡도: O(VE) (V: 정점의 개수, E: 간선의 개수)
• 음수 가중치 처리: 음수 가중치를 가진 간선이 있는 그래프에서도 사용 가능
• 음수 사이클 감지: 음수 사이클의 존재 여부를 확인할 수 있음

동작 원리

벨만-포드 알고리즘은 다음과 같은 단계로 동작합니다:

1. 초기화: 시작 정점의 거리를 0으로, 나머지 정점들의 거리를 무한대로 설정
2. 반복 작업: 모든 간선에 대해 V-1번 반복하여 최단 거리를 갱신
   • 현재 정점까지의 거리 + 간선의 가중치 < 도착 정점까지의 거리
   • 위 조건이 만족되면 도착 정점까지의 거리를 갱신
3. 음수 사이클 검사: 모든 간선을 한 번 더 확인하여 갱신이 발생하면 음수 사이클 존재

구현 예시

def bellman_ford(graph, start, V):
    # 거리 초기화
    distance = [float('inf')] * V
    distance[start] = 0
    
    # V-1번 반복
    for _ in range(V-1):
        for u, v, w in graph:
            if distance[u] != float('inf') and distance[u] + w < distance[v]:
                distance[v] = distance[u] + w
    
    # 음수 사이클 검사
    for u, v, w in graph:
        if distance[u] != float('inf') and distance[u] + w < distance[v]:
            return None  # 음수 사이클 존재
    
    return distance

활용 사례

• 네트워크 라우팅: 네트워크에서 최적의 경로를 찾는데 사용
• 금융 거래: 환율 차이를 이용한 거래 기회 탐색
• 게임 개발: 캐릭터의 최단 경로 탐색, 특히 음수 가중치가 있는 경우

장단점

장점

• 음수 가중치가 있는 그래프에서도 사용 가능