[최단경로 알고리즘 - 3] 벨만 포드 알고리즘

* 벨만 포드 알고리즘이란?

 시작 정점으로부터 다른 정점까지의 최단 경로를 찾기 위한 알고리즘이다. 벨만 포드 알고리즘의 특징은 다음과 같다.

1. 음수 가중치가 있는 그래프의 시작 정점에서 다른 정점까지의 최단 거리를 구할 수 있다.

2. 음수 사이클의 존재 여부를 알 수 있다.

 

 음수 사이클 안에서 무한루프를 도는 경우를 알 수 있는 방법은, 그래프 정점의 개수를 V라고 할 때 인접 간선을 검사하고 거리 값을 갱신하는 과정을 V-1 번으로 제한하면 가능해진다. 그래프의 시작 정점에서 특정 정점까지 도달하기 위해 거쳐 가는 최대 간선 수는 V-1개이기 때문에 V번째 간선이 추가되는 순간 사이클이라고 판단할 수 있게 된다. 벨만 포드 알고리즘의 시간 복잡도는 O(VE)이다. 

 

 매번 모든 간선을 전부 확인하기 때문에 다익스트라 알고리즘에 비해서 시간이 오래 걸리지만 음수 간선 순환을 탐지할 수 있다.

 

* 프로세스

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

2. 최단 거리 테이블을 초기화한다.

3. 다음의 과정을 N-1번 반복한다.

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

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

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

  4-1. 이때 최단 거리 테이블이 갱신된다면 음수 간선 순환이 존재하는 것이다.

 

* python으로 구현한 벨만 포드 알고리즘

import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정
 
def bf(start):
    # 시작 노드에 대해서 초기화
    dist[start] = 0
 
    # 전체 n번의 라운드(round)를 반복
    for i in range(n):
        # 매 반복마다 '모든 간선'을 확인하며
        for cur in range(n):
            for (next_node, cost) in graph[cur]:
                # 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧을 경우
                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())
 
# 모든 간선에 대한 정보를 담는 리스트 만들기
graph = [[] for _ in range(n+1)]
 
# 최단 거리 테이블을 모두 무한으로 초기화
dist = [INF] * (n+1)
 
# 모든 간선 정보를 입력받기
for _ in range(m):
    a, b, c = map(int, input().split())
    # a번 노드에서 b번 노드로 가는 비용이 c라는 의미
    graph[a].append((b, c))
 
# 벨만 포드 알고리즘을 수행
negative_cycle = bf(1) # 1번 노드가 시작 노드
 
if negative_cycle:
    print('-1')
else:
    # 1번 노드를 제외한 다른 모든 노드로 가기 위한 최단 거리 출력
    for i in range(2, n+1):
        # 도달할 수 없는 경우, -1을 출력
        if dist[i] == INF:
            print('-1')
        # 도달할 수 있는 경우 거리를 출력
        else:
            print(dist[i])
 

 

 

* 참고

- https://velog.io/@younge/Python-%EC%B5%9C%EB%8B%A8-%EA%B2%BD%EB%A1%9C-%EB%B2%A8%EB%A7%8C-%ED%8F%AC%EB%93%9CBellman-Ford-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

 

- https://www.youtube.com/watch?v=Ppimbaxm8d8