[알고리즘] 벨만 포드(최단경로에 음수 간선이 있을 때)

본문에 앞서 질좋은 책을 집필해주신 나동빈님한테 감사합니다. 

벨만포드 알고리즘을 최단경로 문제에서 다익스트라 대신 사용해도 문제는 없지만 시간복잡도가 증가하기에 

가급적으로 음수 간선이 존재할 때만 사용해주자

 

최단경로 문제 유형

1) 모든 간선이 양수인 경우

2) 음수 간선이 있는 경우

          2-1) 음수 간선 순환은 없는 경우

          2-2) 음수 간선 순환이 있는 경우

벨만 포드 최단 경로 알고리즘은 음의 간선이 포함된 상황에서도 사용할 수 있다.

     또한 음수 간선의 순환을 감지할 수 있습니다.

     벨만 포드의 기본 시간 복잡도는 O(VE)로 다익스트라 알고리즘에 비해 느리다.

 

벨만 포드 알고리즘 단계

1) 출발 노드를 설정한다.

2) 최단 거리 테이블을 초기화합니다.

3) 다음의 과정을 N-1번 반복합니다.

          3-1) 전체 간선 E개를 하나씩 확인합니다.

          3-2) 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.

만약 음수 간선 순환이 발생하는지 확인하고 싶다면 3번의 과정을 한 번 더 수행한다.

          이때 최단 거리 테이블이 갱신된다면 음수 간선 순환이 존재한다.

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

11657번: 타임머신

# 벨만 포드 알고리즘
import sys
input = sys.stdin.readline
INF = int(1e9)

def bf(start):
    # 시작 노드에 대해서 초기화
    dist[start] = 0
    # 전체 n번의 라운드(round)를 반복
    for i in range(n):
        # 매 반복마다 "모든 간선"을 확인하며
        for j in range(m):
            cur = edges[j][0]
            next_node = edges[j][1]
            cost = edges[j][2]
            # 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
            if dist[cur] != INF and dist[next_node] > dist[cur] + cost:
                dist[next_node] = dist[cur] + cost
                # n번째 라운드에서도 값이 갱신된다면 음수 순환이 존재
                if i == n-1:
                    return True
    return False

n, m = map(int, input().split())
edges = []
dist = [INF] * (n+1)

for _ in range(m):
    a, b, c = map(int, input().split())
    edges.append((a, b, c))

# 벨만 포드 알고리즘을 수행
negative_cycle = bf(1) # 1번 노드가 시작 노드

if negative_cycle:
    print(-1)
else:
    # 1번 노드를 제외한 다른 노드를 가기 위한 최단 거리 출력
    for i in range(2, n+1):
        if dist[i] == INF:
            print(-1)
        else:
            print(dist[i])