벨만 포드 알고리즘 - 백준 11657 (22.7.17)

벨만 포드 알고리즘이란

벨만 포드 알고리즘(Bellman-Ford Algorithm)은 한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘이다.

다익스트라 알고리즘이 모든 가중치가 양수인 경우에만 사용할 수 있는 반면에 벨만-포드 알고리즘은 노드 간의 간선 가중치가 음수인 경우에도 사용할 수 있다.

벨만 포드 알고리즘의 동작

1. 시작 노드를 설정한다.
2. 시작 노드에서 각 다른 노드의 거리 값을 무한대로 설정하고 시작 노드를 0으로 설정한다.
3. 현재 노드의 모든 인접 노드를 탐색하며 기존에 저장된 인접 노드까지의 거리보다 현재 노드를 거치고 인접 노드에 도달하는 게 더 짧을 경우 값을 갱신한다.
4. 3의 과정을 모든 노드에 대해 수행한다.
5. 모든 노드에 3 - 4를 수행하고서 또 거리가 갱신된다면 −∞
   를 발생시키는 음수 사이클이 존재함을 의미한다.

음수 사이클의 문제점

• 사이클이 존재하나 양수값이 더 클 경우 : 사이클을 순환하여도 이득이 없으므로 그대로 진행한다.
• 사이클이 존재하고 음수값이 더 클 경우 : 사이클을 순환할 수록 가중치가 감소해 최소 비용을 찾는 입장에서 사이클을 무한히 순환하고 목적지에 도착함은 실질적인 최단 경로라 보기 어렵다. 적어도 동일 노드를 방문하면 안된다는 등 제약 조건이 있어야 한다.

음수 사이클의 존재 여부 검출

V - 1번만큼 탐색을 마쳤으므로 최단 거리 제약 한계에 도달했다. 이 다음 순회에서도 만약 갱신되는 값이 존재한다면 앞으로도 계속 갱신됨을 의미하므로 음수 사이클이 존재함을 의미한다.

벨만-포드 알고리즘의 시간 복잡도

우선 $|V|−1$번만큼 순회하므로 $O(V)$가 되고 매번 총 $edge(O(E))$만큼 탐색하므로 $O(|V||E|)$가 된다.

그런데 모든 노드에 간선이 연결되어 있다면 라면 $E$는 $V^2$에 근사해지므로 최악의 경우 $O(V^3)$이 된다. 이는 다익스트라 알고리즘이 최악의 경우 $O(V^2)$인 것과 비교했을 때 불리함을 알 수 있다. 따라서 벨만-포드 알고리즘은 간선의 가중치에 음수가 존재할 경우에만 채택해야 한다.

백준 11657번 문제

음의 간선이 존재하는 그래프 내에서 최단 경로를 찾는 벨만-포드 알고리즘을 활용하여 풀 수 있는 문제이다.

import sys
input = lambda : sys.stdin.readline().rstrip()
INF = 987654321

N, M = map(int, input().split())
edges = []
distance = [INF] * (N + 1)
for _ in range(M):
   edges.append(tuple(map(int, input().split())))

def bf(start):
   distance[start] = 0 # 시작 노드에 대해서 거리를 0으로 초기화
   for i in range(N): # 정점 수만큼 반복
       for j in range(M): # 매 반복 마다 모든 간선 확인
           now, next, cost = edges[j]
           # 현재 간선을 거려서 다른 노드로 이동하는 거리가 더 짧은 경우
           if distance[now] != INF and distance[next] > distance[now] + cost:
               if i == N - 1:
                   return True # n-1번 이후 반복에도 값이 갱신되면 음수 순환 존재
               distance[next] = distance[now] + cost
   return False

if bf(1):
   print(-1)
else:
   for i in range(2, N + 1):
       print(distance[i] if distance[i] != INF else -1)