[알고리즘] 벨만 포드 알고리즘

• 벨만 포드(Bellman-Ford) 최단 경로 알고리즘

• 음수 간선이 포함된 상황에서의 최단 경로 문제에 사용되는 알고리즘

• 위의 그래프처럼 모든 간선이 양수라면 다익스트라 알고리즘을 사용하면 된다.

• 하지만 위의 그래프처럼 일부의 음수 간선이 포함된 경우 어떻게 계산할 수 있을까?
• 일부의 음수 간선이 포함된 경우 최단 거리가 음의 무한인 -INF가 나오는 노드가 생길 수 있다.

벨만 포드 최단 경로 알고리즘

• 음수 간선에 관하여 최단 경로 문제는 다음과 같이 분류할 수 있다.

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

벨만 포드 최단 경로 알고리즘 동작 과정

• 최단 경로 알고리즘인 다익스트라 알고리즘과 벨만 포드 알고리즘의 차이점은 다음과 같다.
  

벨만 포드 최단 경로 알고리즘 소스코드

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

def bf(start):
    # 시작 노드에 대해서 초기화
    dist[start] = 0
    # 전체 n번의 라운드(round)를 반복(n-1번의 반복)
    for i in range(n):
    	# 매 반복마다 m개의 모든 간선을 확인
    	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())
    # a번 노드에서 b번 노드로 가는 비용이 c라는 의미
    edges.append((a, b, c))

# 벨만 포드 알고리즘 수행
# 1번 노드가 시작 노드
negative_cycle = bf(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])