[Python] 백준 11657. 타임머신 (Bellman Ford)

BellmanFord 알고리즘

Bellman Ford 알고리즘은 다익스트라 알고리즘을 개선시킨 알고리즘이다.

• 장점
  • 음수 가중치로 인한 음의 사이클 형성 방지 (음수 간선에도 적용할 수 있는 알고리즘!)
    • 음수 가중치 자체는 문제가 되지는 않는다. 그러나 만약 음수 가중치가 포함된 음의 사이클이 형성될 경우, 다익스트라는 비용을 계속 낮출 수 있는 사이클을 계속 돌 것이고, 그럼 알고리즘은 무한 루프에 빠지게 됨.
    • 그러나 벨만 포드는 음의 사이클이 형성되었을 경우 탐색을 멈춤.

음의 사이클이 형성된 건 어떻게 아느냐?

정점 개수 N에 대하여 간선 최대 개수는 N-1이므로 모든 정점에 대하여 N-1번 반복하면 모두 갱신할 수 있다. 따라서 N번째 반복에서 최단 경로가 또 한번 갱신된다면 이는 무한히 갱신되는 음의 사이클이 형성되었음을 알 수 있음. 그래서 N번째 반복에서 갱신되면 사이클이 형성됐음을 알리는 False 출력, 아니면 정상적으로 갱신되었음을 알리는 True를 반환.

• 단점
  • 벨만포드는 다익스트라보다 시간복잡도가 더 비효율적!
    • 다익스트라는 그리디하게 출발 노드부터 최소 거리인 노드를 반복적으로 찾아 최소 거리/비용 계산함. 하지만, 벨만포드는 다익스트라와 달리 모든 경우의 수를 고려하는 동적 계획법이 사용됨. 매 단계마다 모든 간선을 전부 확인해서 최소 거리를 업데이트함.이때, 다익스트라는 출발노드에서만 연결된 노드를 반복적으로 탐색하며 다른 모든 노드까지의 최소 거리를 구하지만, 벨만 포드는 모든 노드가 한번씩 출발점이 되어 다른 노드까지의 최소 비용을 구함.
    • 다익스트라 O(ElogV), 벨만포드 O(VE) (E: 간선 개수, V: 정점 개수)

코드

import sys
from math import inf

input = sys.stdin.readline


def BellmanFord():
    dist[0], dist[1] = 0, 0

    for n in range(N):
        for start, end, d in edge:
            cost = dist[start] + d
            if cost < dist[end] and dist[start] != inf:  # dist[x]=inf인 경우 최단 경로가 없음을 의미하므로 건너뛰기
                dist[end] = cost
                if n == N - 1:
                    return False
    return True


if __name__ == '__main__':
    N, M = map(int, input().split())
    edge = [list(map(int, input().split())) for _ in range(M)]
    dist = [inf for _ in range(N + 1)]

    if BellmanFord():
        for i in range(2, N + 1):
            print(dist[i] if dist[i] != inf else -1)
    else:
        print(-1)