벨만 포드 알고리즘

• 음수 간선이 포함된 상황에서의 최단 거리 문제
• 시간 복잡도 O(VE)
  • 다익스트라 알고리즘에 비해 느림
• 동작 원리
  1. 출발 노드를 설정합니다.
  2. 최단 거리 테이블을 초기화합니다.
  3. 다음의 과정을 N-1번 반복합니다.
     1. 전체 간선 E개를 하나씩 확인합니다.
     2. 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신합니다.
• 만약 음수 간선 순환이 발생하는지 체크하고 싶담면 3번의 과정을 한 번 더 수행합니다.
  • 이때 최단 거리 테이블이 갱신된다면 음수 간선 순환이 존재하는 것입니다.
• 다익스트라 vs 벨만 포드
  • 다익스트라
    • 매번 방문하지 않는 노드 중에서 최단 거리가 가장 짧은 노드를 선택합니다.
    • 음수 간선이 없다면 최적의 해를 찾을 수 있습니다.
  • 벨만 포드
    • 매번 모든 간선을 전부 확인합니다.
      • 따라서 다익스트라 알고리즘에서의 최적의 해를 항상 포함합니다.
    • 다익스트라 알고리즘에 비해서 시간이 오래 걸리지만 음수 간선 순환을 탐지할 수 있습니다.
• 기본 코드

import sys
input = sys.stdin.readline
INF = int(1e9)

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

# 간선에 대한 정보
for _ in range(m):
	start, end, money = map(int,input().split())
    edges.append((start,end,money))
    
# 벨만 포드 알고리즘
def bf(start):
	# 시작 노드에 대해서 초기화
    dist[start] = 0
    # 전체 n번의 라운드를 반복
    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

negative_cycle = bf(1) # 1번 노드가 시작 노드