🔒 개념
🔎 음수 가중치를 허용하는 그래프에서 최단 경로를 구하는 알고리즘.
- 매 단계마다 모든 간선의 가중치를 다시 확인하여 최소비용을 갱신해 하나의 정점에서 출발하는 최단 거리를 구한다.
- 음수 사이클이 없어야 한다.
O(nm)시간 복잡도를 가진다.- DP 사용, relaxation 기법
🔓 동작 단계
-
시작 노드를 설정한 다음 시작 노드의 최소 비용은 0, 나머지 노드는 INF로 초기화한다. 이후 최소 비용을 갱신할 때 직전 노드도 갱신한다.
-
노드 개수 – 1만큼 다음 연산을 반복한다.
2-1. 시작 노드에서 갈 수 있는 각 노드에 대하여 전체 노드 각각을 거쳐갈 때 현재까지 구한 최소 비용보다 더 적은 최소 비용이 있는지 확인하여 갱신한다. 최소 비용을 갱신할 때, V의 직전 노드 값도 같이 갱신한다.
-
과정 2를 마지막으로 한 번 더 수행하여 갱신되는 최소 비용이 있는지 확인. 만약 있다면 음의 순환이 있음을 의미한다.
벨만-포드 알고리즘은 글로만 읽으면 쉽게 와닿지 않습니다. 아마도 ‘노드 개수 – 1만큼 연산을 반복하라’는 말과 과정 3의 ‘한 번 더 수행하라’는 말이 쉽게 와닿지 않을 겁니다. 우선은 벨만-포드 알고리즘이 동작하는 과정을 자세히 살펴보고 그 이후에 왜 그렇게 하는지에 대해 설명해보겠습니다.
🔓 동작 과정 (그림)
- 우선 시작 노드를 A로 정하고 최소 비용을 0, 직전 노드를 A, 나머지 노드는 INF로 초기화
- 노드 A에서 A를 거쳐 각 노드 B, C, D, E까지 가는 비용 중 현재까지 구한 최소 비용보다 적은 값이 있는지 확인하고 현재까지 구한 최소 비용보다 비용이 적다면 갱신
- 해당 정점의 최소 비용은 최소_비용(A)(숫자), 가중치가 있는 간선은 간선(A, B)(숫자) 표시, 간선이 없는 경우는 INF로 계산한다고 했을 때,
⏰
최소비용(A)(0) == 최소비용(A)(0) + 간선(A, A)(0) : 갱신하지 않음
최소비용(B)(INF) > 최소비용(A)(0) + 간선(A, B)(4) : 최소비용(B)를 INF에서 4로 갱신
최소비용(C)(INF) > 최소비용(A)(0) + 간선(A, C)(3) : 최소비용(C)를 INF에서 3으로 갱신
최소비용(D)(INF) == 최소비용(A)(0) + 간선(A, D)(INF) : 갱신하지 않음
최소비용(E)(INF) > 최소비용(A)(0) + 간선(A, E)(-6) : 최소_비용(E)를 -6으로 갱신
- 노드 A에서 B를 거쳐 각 노드까지 가는 최소 비용도 갱신
⏰
최소비용(A)(0) < 최소비용(B)(4) + 간선(B, A)(INF) : 갱신하지 않음
최소비용(B)(4) == 최소비용(B)(4) + 간선(B, B)(0) : 갱신하지 않음
최소비용(C)(3) < 최소비용(B)(4) + 간선(B, C)(INF) : 갱신하지 않음
최소비용(D)(INF) > 최소비용(B)(4) + 간선(B, D)(5) : 9로 갱신
최소비용(E)(-6) < 최소비용(B)(4) + 간선(B, E)(-6) : 갱신하지 않음
- 노드 A에서 C를 거쳐 각 노드까지 가는 최소 비용도 갱신
- ex) 노드 C를 거쳐서 B로 가는 새 경로(5)는 기존의 B의 최소 비용(4)보다 크므로 갱신하지 않는다.
⏰
최소비용(A)(0) < 최소비용(C)(3) + 간선(C, A)(INF) : 갱신하지 않음
최소비용(B)(4) < 최소비용(C)(3) + 간선(C, B)(2) : 갱신하지 않음
최소비용(C)(3) == 최소비용(C)(3) + 간선(C, C)(0) : 갱신하지 않음
최소비용(D)(9) < 최소비용(C)(3) + 간선(C, D)(INF) : 갱신하지 않음
최소비용(E)(-6) < 최소비용(C)(3) + 간선(C, E)(INF) : 갱신하지 않음
- 노드 A에서 D를 거쳐가는 방법은 없으므로 갱신하지 않는다
- 노드 A에서 E를 거쳐 각 노드까지 가는 최소 비용도 갱신.
- 모든 최단 경로에 대해 노드의 최소 비용을 체크했으므로, 벨만-포드 알고리즘의 첫 번째 반복이 끝!!
⏰
최소비용(A)(0) < 최소비용(E)(-6) + 간선(E, A)(INF) : 갱신하지 않음
최소비용(B)(4) < 최소비용(E)(-6) + 간선(E, B)(2) : 갱신하지 않음
최소비용(C)(3) == 최소비용(E)(-6) + 간선(E, C)(0) : -4로 갱신
최소비용(D)(9) < 최소비용(E)(-6) + 간선(E, D)(INF) : 갱신하지 않음
최소비용(E)(-6) < 최소비용(E)(-6) + 간선(E, E)(INF) : 갱신하지 않음
- 첫번째 반복이 끝난 결과.
- 위에 했던 과정을 '노드 개수 - 1'번을 반복한다.
⏰
+ : 노드 A에서 A를 거쳐 각 노드까지 가는 비용을 갱신
최소비용(A)(0) == 최소비용(A)(0) + 간선(A, A)(0) : 갱신하지 않음
최소비용(B)(4) == 최소비용(A)(0) + 간선(A, B)(4) : 최소비용(B)를 INF에서 4로 갱신
최소비용(C)(-4) < 최소비용(A)(0) + 간선(A, C)(3) : 갱신하지 않음
최소비용(D)(9) > 최소비용(A)(0) + 간선(A, D)(INF) : 갱신하지 않음
최소비용(E)(-6) == 최소비용(A)(0) + 간선(A, E)(-6) : 최소비용(E)를 -6으로 갱신
📌 특징
❓ 왜 정점 개수 -1만큼 반복?
❗ 매 연산마다 최단 경로가 1개씩 확정되므로!
- 그래프에서 시작 노드에서 다른 노드로 가는 최단 경로는 최대 V - 1개의 간선을 포함한다.
- 따라서 :
1번째 반복에서 1개 간선을 통해 도달 가능한 최단 거리 업데이트.
2번째 반복에서 2개의 간선을 통해 도달 가능한 최단 거리 업데이트.
...
(V - 1)번째 반복에서 최대 V - 1개의 간선을 통해 도달 가능한 최단 거리 업데이트.
❓ 왜 한번 더 연산을 반복?
❗ 음수 사이클로 인해 최단 거리가 무한히 줄어드는지 확인하기 위해서
추가로 한 번 더 반복하여 모든 간선을 검사하면, distance[u] + w < distance[v] 조건을 만족하는 간선이 발견될 경우, 이는 음수 가중치 사이클이 존재한다는 것을 의미한다. 따라서, 한 번 더 반복은 음수 가중치 사이클 검출에 필수적이다.
⭐ 정리
그래프에 음의 순환이 있으면 어떤 알고리즘도 최단 경로를 구할 수 없다 ! 벨만 포드 알고리즘은 음의 가중치가 있는 그래프에서 최단 경로를 찾을 수 있는 대신, 음의 순환에 빠질 수 있고, 다익스트라 알고리즘은 음의 가중치가 있는 그래프에서 동작하지 못하므로 아예 언급이 안된다.
📚 예제
위와 같은 그래프가 있을 때 1번 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 문제를 생각해보자.
📁 Step 1. 에지리스트 구현 및 리스트 초기화
-
벨만 - 포드 알고리즘은 간선을 중심으로 동작(모든 간선을 확인)하므로 그래프를 에지 리스트로 구현한다.
-
최단 경로 리스트
- 출발 노드는 0, 나머지 노드는 무한대로 초기화한다.
- 출발 노드를 1로 선택해 벨만 - 포드 알고리즘을 진행
📁 Step 2. 간선 확인 1.
-
벨만 포드 알고리즘은 매 반복마다 모드 간선을 확인한다.
-
모든 에지의 (출발, 종료, 가중치)에서 다음 조건을 만족하면 업데이트를 실행한다.
- 출발 노드가 무한대가 아니고, `종료 노드값 < 출발 노드 값 + 에지 가중치` 이면 `종료 노드 값 = 출발 노드값 + 에지 가중치`로 업데이트 - 즉, D[s] != INF and D[e] > D[s] + w 일 때 D[e] = D[s] + w
- 간선 1의 경우 출발 노드 1의 값이 무한이 아니므로(0) 조건을 확인한다.
- distance[2] = distance[1] + 8 = 8 < 무한 이므로 값을 갱신한다
- 간선 2의 시작 노드는 2인데, 이전에 값이 무한에서 8로 갱신되었으므로 조건을 확인한다.
- distance[5] = distance[2] + 5 = 13 < 무한 이므로 값을 갱신한다
- 간선 3의 경우 시작 노드 1의 값이 무한이 아니므로 조건을 확인한다.
- distance[3] = distance[1] + 3 = 3 < 무한 이므로 값을 갱신한다.
- 간선 4의 경우 시작 노드 3의 값이 이전에 무한에서 3으로 갱신되었으므로 조건을 확인한다.
- distance[4] = distance[3] + 7 = 10 < 무한 이므로 값을 갱신한다
- 간선 5의 경우 시작 노드 4의 값이 이전에 무한에서 10으로 갱신되었으므로 조건을 확인한다.
- distance[2] = distance[4] + -4 = 6 < 8 이므로 값을 갱신한다.
- 간선 6의 경우 시작 노드 5의 값이 이전에 무한에서 13으로 갱신되었으므로 값을 확인한다.
- distance[4] = distance[5] + -2 = 11 > 10 이므로 값을 갱신하지 않는다.
📁 Step 3. 간선 확인 N-1번 수행
📌 STEP 2을 N-1번 (N : 노드 개수) 수행한다.
- N-1번 수행한 후의 최단 경로 리스트 값.
📁 Step 4. N번 수행 후 감소하는 값이 있는지 확인
- 위의 경우 Node 4의 값이 감소했으므로 음의 사이클이 존재.
⏰ 구현
🗒 슈도 코드
n(노드 개수), m(에지 개수)
edges(에지 정보 저장 리스트)
distance(거리 리스트) # 무한으로 초기화
for 에지 개수만큼 반복
(s, e, w) # 에지 리스트에 에지 정보 저장
# 벨만 포드 수행
거리 리스트에 출발 노드 0으로 초기화
for 에지 개수 만큼 반복
현재 에지 데이터 가져오기
if 출발 노드가 무한대가 아니고 종료 노드 값 < 출발 노드 값 + 에지 가중치:
업데이트 수행 -> 종료 노드 값 = 출발 노드 값 + 에지 가중치
if n 번째 라운드:
음수 사이클 존재
음수 사이클 존재하면 -> -1 출력
음수 사이클 존재하지 않으면 -> 거리 리스트 출력🗒 파이썬 코드
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])