⭐️ 벨만-포드 알고리즘(Bellman-Ford algorithm)

• 특정 출발 노드에서 다른 모든 노드까지의 최단 경로 탐색
• 음수 가중치 에지가 있어도 수행할 수 있음
• 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있음
• 시간 복잡도 $O(VE)$ (V: 노드 수, E: 에지 수)

벨만 포드 알고리즘 vs 다익스트라 알고리즘

• 다익스트라 알고리즘
  • 매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
  • 음수 간선이 없다면 최적의 해를 찾을 수 있다.
• 벨만 포드 알고리즘
  • 매번 모든 간선을 전부 확인한다.
    • 따라서 다익스트라 알고리즘에서의 최적의 해를 항상 포함한다.
  • 다익스트라 알고리즘에 비해서 시간이 오래 걸리지만 음수 간선 순환을 탐지할 수 있다.

벨만 포드 알고리즘 수행 과정

1. 출발 노드를 설정한다.
2. 최단 거리 테이블을 초기화한다.
3. 다음의 과정을 노드개수-1번 반복한다.
   1. 전체 간선 E개를 하나씩 확인한다.
   2. 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
      → 출발 노드가 방문한 적 없는 노드(출발거리 == INF)일 때 값을 업데이트 하지 않는다.
      → 출발 노드의 거리 리스트값 + 에지 가중치 < 종료 노드의 거리 리스트 값 일 때 종료 노드의 거리 리스트 값을 업데이트 한다.
4. 만약 음수 간선 순환이 발생하는지 체크하고 싶다면 3번의 과정을 한 번 더 수행한다.
   → 이 때 최단 거리 테이블이 갱신된다면 음수 간선 순환이 존재하는 것이다.

예시를 통해 알고리즘 동작 원리를 자세히 살펴보자.

• 다음과 같은 그래프가 있을 때 1번 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 문제를 생각해보자.

STEP 1

• 에지 리스트
  • 벨만 - 포드 알고리즘은 간선을 중심으로 동작(모든 간선을 확인)하므로 그래프를 에지 리스트로 구현한다.
    

STEP 2

• 최단 경로 리스트
  • 출발 노드는 0, 나머지 노드는 무한대로 초기화한다.
  • 출발 노드를 1로 선택해 벨만 - 포드 알고리즘을 진행해보자.
    

STEP 3

• 벨만 포드 알고리즘은 매 반복마다 모드 간선을 확인한다.
• 모든 에지의 (출발, 종료, 가중치)에서 다음 조건을 만족하면 업데이트를 실행한다.
  • 출발 노드가 무한대가 아니고, 종료 노드값 < 출발 노드 값 + 에지 가중치 이면 종료 노드 값 = 출발 노드값 + 에지 가중치로 업데이트
  • 즉, 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 4

• STEP 3을 N-1번 (N : 노드 개수) 수행한다.
  • N-1 번 수행하는 이유는 다음과 같다.
    • 그래프에 N개의 노드가 있다면, 출발 노드에서 다른 모든 노드로 가는 최단 경로는 최대 N-1개의 간선을 사용할 수 있다.
    • 따라서 N-1번의 반복을 수행하여 모든 노드에 대한 최단 경로를 찾을 수 있다.
• 반복문을 N-1번 수행한 후의 최단 경로 리스트의 값은 다음과 같다.
  
• 만약 N번째 반복에서 최단 경로가 업데이트된다면, 이는 음수 사이클이 존재한다는 것을 의미한다.
  • 위와 같은 경우에서 한번 더 반복문을 수행한 후의 최단 경로 리스트 값은 다음과 같다.
    • 노드 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])

📝 관련 문제

• BOJ - 11957 : 타임머신
• BOJ - 1219 : 오민식의 고민

📍 References

• Do it 알고리즘 코딩 테스트 파이썬 편
• 하루코딩 유튜브
• 동빈나 유튜브