벨만-포드 알고리즘 이해하기 ([백준] 11657번 타임머신)

벨만-포드 알고리즘이란?

벨만-포드 알고리즘은, 한 노드에서 다른 노드까지의 거리를 구하는 알고리즘이다.
다익스트라 알고리즘이 모든 비용(가중치)가 양수인 경우에만 사용할 수 있는 반면에 
벨만-포드 알고리즘은 노드 간의 간선 비용(가중치)가 음수인 경우에도 사용할 수 있다. 
다만, 시간 복잡도는 벨만-포드가 더 크기 때문에 비용(가중치)가 모두 양수라면 굳이 벨만-포드를 사용할 필요는 없다.

 

음수 사이클이 문제가 되는 이유

 

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

최단 거리는 순환되어서는 안된다는 가정을 담고 있으므로 경로(Edge)길이는 |V|−1이 된다.

 

벨만-포드 알고리즘의 동작

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

 

위 그래프는 음수 사이클이 존재한다.
벨만 - 포드 알고리즘을 적용하여 최단 거리를 구하는 과정을 살펴보자.
시작점은 s라고 가정하자.

우선 최단거리 테이블에서 시작 노드를 0으로 초기화하고 나머지 노드에 대해 ∞으로 설정한다.

s의 인접노드는 a, c, e로, 각각 3, 5, 2를 최단거리 테이블에 저장한다. (INF보다 작기 때문)

s의 인접노드를 모두 탐색했으니 a노드를 현재 노드로 옮긴다.  
a의 인접노드는 b뿐이다.  
a노드에서 b노드로 가는 경로는 3 + (-4)= -1 인데  -1 < INF 이므로  최단거리 테이블에서 b를  -1로 갱신해준다.

b의 인접노드는 g노드 뿐이다. 
b에서 g로 가는 경로는 -1 + 4 = 3 인데, 3 < INF 이므로 최단거리테이블에서 g를 3으로 갱신해준다.

c노드의 인접 노드는 d노드 뿐이다.
c에서 d로 가는 경로는 5 + 6 = 11 인데, 11 < INF이므로 최단거리테이블에서 d를  11로 갱신해준다.

d노드의 인접 노드는 c와 g이다. 
d노드에서 c로 가는 경로는 11 + (-3) = 8인데, 8 > 5 이므로 최단거리테이블의 c에 저장해두었던 5를 그대로 유지한다.
d노드에서 g로 가는 경로는 11 + 2 = 13 인데, 13 > 2 이므로 최단거리테이블의 g에 저장해두었던 2를 그대로 유지한다.

e 노드의 인접 노드는 f로,
e에서 f로 가는 경로는 2 + 3 = 5 인데, 5 < INF 이므로 최단거리 테이블에서 f를 5로 갱신한다.

f의 인접 노드는 e와 g이다.
f에서 e로 가는 경로는 5 - 6 = -1 인데, -1 < 2이므로 최단거리 테이블에서 e를 -1로 갱신해준다.
f에서 g로 가는 경로는 5 + 1 = 6 인데, 6 > 2 이므로 최단거리 테이블의 g인 2를 그대로 유지한다.

이로서, v-1 개의 노드에 대해 모두 탐색을 종료했다.
그런데, 그래프에서 볼 수 있듯이 e와 f사이엔 음수 사이클이 존재하여 해당 사이클을 무한히 순회하면,
모든 노드에 대해 -∞ 가 될 수 있다.

따라서 동일 노드를 방문하지 않는다는 제약조건이 있어야 하고, 
만약 그러한 조건이 없다면, 경로가 존재할 수 없음을 의미하는 (-1)을 출력하는 등의 조치를 취해서
경로가 없음을 표현해야 한다.

음수 사이클의 존재 여부 검출은 간단하다. v-1 번 만큼의 탐색을 마쳤으므로 최단 거리 제약 한계에 도달했다.
이 다음 순회에서도 만약 갱신되는 값이 존재한다면, 앞으로도 계속 갱신됨을 의미한다.
이는 곧, 음수 사이클이 존재함을 의미하는 것이라고 할 수 있다.

 

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

우선 |V| - 1 번 만큼 순회하므로 O(V)가 되고 매번 총 edge(O(E))만큼 탐색하므로 O(|V||E|)가 된다.
그런데 dense graph라면 E는 V^2에 근사해지므로 최악의 경우 시간복잡도가 O(V^3)가 된다.
이는 다익스트라 알고리즘이 최악의 시간복잡도가 O(V^2)인 것과 비교했을 때와 비교하여 벨만-포드가 훨씬 불리함을 알 수 있다.
따라서 벨만-포드 알고리즘은 간선의 비용(가중치)에 음수가 존재할 경우에만 채택해야 한다.

위의 예시에 대한 입력
8 11
1 2 3
1 3 5
1 4 2
2 5 -4
3 6 6
4 7 3
5 8 4
6 3 -3
6 8 2
7 4 -6
7 8 1

 

백준 11657번 타임머신 

https://www.acmicpc.net/problem/11657

11657번: 타임머신

풀이 코드

import sys

# 노드의 개수 n개, 간선의 개수 m개
n, m = map(int, sys.stdin.readline().rstrip().split())

# 모든 간선에 대한 정보를 담는 리스트 만들기
edges = []

# 무한(10억)을 의미하는 INF 변수 선언
INF = int(1e9)

# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n + 1)

# 모든 간선의 정보 입력
for _ in range(m):
    a, b, c, = map(int, sys.stdin.readline().rstrip().split())
    # a에서 v로 가는 비용이 c
    edges.append((a, b, c))

def bellman_ford(start):
    # 시작 노드에 대해서 초기화
    distance[start] = 0
    # 전체 n번을 반복
    for i in range(n):
        # 매 반복마다 '모든 간선'을 확인한다.
        for a, b, c in edges:
            # 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우, 거리 테이블 갱신
            if distance[a] != INF and distance[b] > distance[a] + c:
                distance[b] = distance[a] + c
                # n번째 라운드에서도 값이 갱신된다면 음수 순환이 존재
                if i == n - 1:  # n - 1번 이후 반복에도 값이 갱신되면 음수 순환 존재
                    return True
    return False


if bellman_ford(1): # 음수 순환이 존재한다면 -1 출력
    print(-1)
else:
    # 1번 노드를 제외한 다른 모든 노드로 가기 위한 최단 거리 출력
    for i in range(2, n + 1):
        # 도달할 수 없는 경우, -1을 출력
        if distance[i] == INF:
            print(-1)
        # 도달할 수 있는 경우 거리를 출력
        else:
            print(distance[i])