음수 가중치가 있는 그래프의 최단 경로

벨만-포드 알고리즘

벨만-포드 알고리즘은 최단 경로를 구하는 알고리즘 중 하나로, 다익스트라 알고리즘과 비슷한 역할을 한다. 하지만 중요한 차이점은 음수 가중치가 있는 그래프에서도 최단 경로를 구할 수 있다는 부분이다. 이 점 때문에 다익스트라와는 다른 방식으로 동작한다.

다익스트라 알고리즘과의 차이

• 다익스트라 알고리즘은 음수 가중치가 없는 그래프에서 사용된다. 이 알고리즘은 우선순위 큐를 사용하여 최단 거리를 찾는데, 시간 복잡도는 O((V + E) * log V)이다. 여기서 V는 정점의 수, E는 간선의 수를 의미한다.
• 반면, 벨만-포드 알고리즘은 음수 가중치를 가진 그래프에서도 최단 경로를 계산할 수 있다. 다만, 시간 복잡도가 더 높아진다. 벨만-포드는 O(V + E)로 동작하지만, 최악의 경우까지 고려하려면 이 과정을 n-1번 반복해야 하므로 시간이 더 오래 걸린다.

알고리즘 동작 방식

1. distance 배열 선언

   • 처음에는 모든 정점의 거리를 무한(INF) 으로 초기화
   • 시작 정점의 거리는 0으로 설정

2. 거리 갱신하기

   • 모든 간선 정보를 하나씩 확인하며, 각 간선(a, b, cost)에 대해 거리를 갱신한다.
   • (a, b) 간선에서 a를 지나서 b로 가는 거리가 더 짧다면, distance[b]를 갱신
   • 이 과정은 n-1번 반복한다. (최단 경로는 최악의 경우 최대 n-1번의 간선을 거칠 수 있기 때문)

3. 한 번 더 거리 갱신하기

   • 모든 간선 정보를 한 차례 더 갱신한다
   • 만약 이번 갱신에서 최단 거리가 더 짧아진 경우, 해당 그래프에는 음수 사이클이 존재한다는 의미이다.
   • 음수 사이클이란, 한 정점으로 돌아가는 길이 계속해서 길이를 줄여가는 순환 구조를 의미한다. 이 경우, 최단 거리가 무한히 줄어들 수 있기 때문에 유효하지 않은 입력으로 간주하고 결과를 반환한다.

음수 사이클 처리

• 벨만-포드 알고리즘에서는, 마지막 한 번의 갱신 과정에서 만약 거리가 갱신되었다면, 그 그래프에는 음수 사이클이 존재한다고 판별할 수 있다.
• 음수 사이클이 존재하는 그래프는, 도달할 수 있는 어떤 지점이라도 무한히 짧은 경로를 가질 수 있기 때문에, 그런 그래프는 최단 경로 문제에서 유효하지 않다고 판단한다.

벨만-포드 알고리즘 예시 코드

def bellman_ford(n, edges, start):
    # 1. 최단 거리 배열 초기화 (무한대로 설정)
    dist = [float('inf')] * n
    dist[start] = 0  # 시작 정점의 거리는 0
    
    # 2. Relaxation 단계: n-1번 반복
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    # 3. 음수 사이클 검사
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            print("음수 사이클이 존재합니다.")
            return None

    return dist

n, start = 5, 0  # 정점 수, 시작 정점
edges = [ ... ]  # 간선 정보(a, b, cost)를 담은 리스트

result = bellman_ford(n, edges, start)
print(result)

추천 문제

타임 머신 (골드 4)

• https://www.acmicpc.net/problem/11657

웜홀 (골드 3)

• https://www.acmicpc.net/problem/1865