벨만 포드 알고리즘

최단 경로 문제에서 모든 간선의 비용이 양수라면 다익스트라 최단 경로 알고리즘을 사용하면 됩니다.

그렇다면 음수 간선이 포함되는 경우에는 어떻게 문제를 해결해야 할까요?

단순히 음수 간선이 포함되는 것만으로는 다익스트라 알고리즘을 이용하여 문제를 해결할 수 있습니다. 하지만 음수 간선의 순환이 포함된다면 최단 거리가 음의 무한인 노드가 발생할 것입니다.

이 경우에 사용하는 방법이 벨만 포드 알고리즘입니다.
벨만 포드 알고리즘은 다익스트라 알고리즘을 알고 있다는 가정 하에 설명합니다.

최단 경로 문제 분류

최단 경로 문제는 다음과 같이 분류할 수 있습니다.

1. 모든 간선이 양수인 경우
2. 음수 간선이 있는 경우
   a. 음수 간선 순환이 없는 경우
   b. 음수 간선 순환이 있는 경우

벨만 포드 최단 경로 알고리즘은 음의 간선이 포함된 상황에서도 사용할 수 있습니다. 또한, 음수 간선의 순환을 감지할 수 있습니다.
벨만 포드의 기본 시간 복잡도는 O(VE)로 다익스트라 알고리즘에 비해 느립니다.

벨만 포드 알고리즘

동작은 다음과 같습니다.

1. 출발 노드를 설정합니다.
2. 최단 거리 테이블을 초기화합니다.
3. 다음의 과정을 N-1번 반복합니다.
   1) 전체 간선 E개를 하나씩 확인합니다.
   2) 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신합니다.

만약 음수 간선 순환이 존재하는지 체크하고 싶다면 3번의 과정을 한 번 더 수행합니다.
이때 최단 거리 테이블이 갱신된다면 음수 간선 순환이 존재하는 것입니다.

구현

import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정

# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())
# 모든 간선에 대한 정보를 담는 리스트 만들기
edges = []
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n + 1)

# 모든 간선 정보를 입력받기
for _ in range(m):
    a, b, c = map(int, input().split())
    # a번 노드에서 b번 노드로 가는 비용이 c라는 의미
    edges.append((a, b, c))

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

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

if negative_cycle:
    print("-1")
else:
    # 1번 노드를 제외한 다른 모든 노드로 가기 위한 최단 거리를 출력
    for i in range(2, n + 1):
        # 도달할 수 없는 경우, -1을 출력
        if distance[i] == INF:
            print("-1")
        # 도달할 수 있는 경우 거리를 출력
        else:
            print(distance[i])

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

1. 다익스트라 알고리즘
   • 매번 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택합니다.
   • 음수 간선이 없다면 최적의 해를 찾을 수 있습니다.
2. 벨만 포드 알고리즘
   • 매번 모든 간선을 전부 확인합니다.
     -> 따라서 다익스트라 알고리즘에서의 최적의 해를 항상 포함합니다.
   • 다익스트라 알고리즘에 비해 시간이 오래 걸리지만 음수 간선 순환을 탐지할 수 있습니다.