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

벨만 포드란?

음수 가중치가 있는 그래프에서도
단일 출발점에서 모든 정점까지의 최단 경로를 구할 수 있는 알고리즘.

다익스트라 알고리즘은 음수 가중치를 허용하지 않지만, 벨만 포드는 이를 허용하며, 음수 사이클 존재 여부도 판별할 수 있다.

전제 조건

조건	설명
그래프 종류	방향 그래프
간선 가중치	음수 허용, 단 음수 사이클 탐지 필요
목적	한 정점에서 모든 정점까지의 최단 거리 (One-To-All)

동작 원리

벨만 포드는 다음과 같은 방식으로 진행된다.

1. 모든 간선 (u -> v)에 대해 다음을 V-1번 반복한다.

if dist[v] > dist[u] + cost:
	dist[v] = dist[u] + cost

2. 위 작업을 정점 개수(V)보다 하나 적은 횟수만큼 반복하면 모든 최단거리가 안정적으로 수렴하게 된다.

3. 이후 한 번 더 반복했을 때 값이 갱신되면, 음수 사이클이 존재하는 것이다.

시간 복잡도는 $O(V \times E)$이다.

간선을 $V-1$번 반복하면서 모두 확인하므로, 간선 수가 많거나 정점이 많을 경우 느릴 수 있다.

즉, 음수 가중치가 존재하지 않는다면 다익스트라 알고리즘을 사용하는게 좋고(더 빠름), 음수 가중치가 존재할 때 사용하기 좋다.

구현

음수 가중치가 있는 그래프 문제인 #11657. 타임머신을 봐보자.

$N$개의 도시와 $M$개의 버스가 있으며, 버스를 타고 이동하는 시간이 0이면 순간이동, 0보다 작으면 타임머신을 이용해 시간을 되돌아가는 상황이다. (음수 가중치)

앞서 설명한 벨만-포드 알고리즘을 적용하여 구현해보자.

def bellman_ford(n: int, edges: list) -> list:
	dist = [float("inf")] * (n + 1)
	dist[1] = 0
	for i in range(1, n + 1):
		for s, e, cost in edges:
			if dist[s] != float("inf") and dist[e] > dist[s] + cost:
				dist[e] = dist[s] + cost
				if i == n: return [-1]	# n번째 반복에서도 갱신된다면 음수 사이클 존재
	# INF의 경우 도달 불가능한 도시이므로 -1
	for i in range(2, len(dist)):
		if dist[i] == float("inf"): dist[i] = -1
	return dist[2:]

시작 노드는 1번으로 설정하여 거리를 0으로 초기화하고, 도시 수($N$)만큼 반복하며 최단 거리를 갱신한다.

모든 간선에 대해 현재 노드에서 다음 노드로 가는 비용이 더 적으면 갱신하고, 이 과정을 반복한다.

만약 마지막($N$번째) 반복에서도 거리 갱신이 발생하면, 이는 음수 사이클이 존재하는 것이므로 -1을 반환한다.

최종적으로 각 도시별 최단 거리를 계산하고, 도달할 수 없는 도시는 -1로 표시한다.