그래프에서 최단거리를 구하는 알고리즘은 여러개가 있습니다.
BFS, 다익스트라, 벨만-포드, 플로이드-워셜... 그 중에서 오늘은 벨만-포드에 대해 알아봅시다.

👀 'Do it! 알고리즘 코딩테스트 with Python(김종관 저)'을 공부하고 정리한 내용입니다.

1. 개념

벨만-포드 알고리즘은 다익스트라 알고리즘과 동일한 식을 사용하여 시작 노드로부터 각 노드의 최단 거리를 찾습니다. 여기서 다익스트라와 다른점은, 음수 가중치가 있어도 수행이 가능하다는 겁니다. 그렇기에 전체 그래프에서 음수 사이클의 존재 여부를 판단하는데 활용하기도 합니다.

2. 원리 이해하기

2-1. 에지 리스트로 그래프를 구현하고 최단 경로 리스트 초기화하기

벨만-포드 알고리즘은 에지를 중심으로 동작하므로 그래프를 에지 리스트로 구현합니다. 또한 최단 경로 리스트(정답 리스트)를 출발 노드는0, 나머지 노드는 무한대로 초기화합니다. 다음 예에서 출발 노드를 1로 선택해 벨만-포드 알고리즘을 진행하며 알아보겠습니다.

2-2. 모든 에지를 확인해 최단 경로 리스트 업데이트하기

최단 거리 리스트에서 업데이트 반복 횟수는 노드 개수 -1입니다. 노드 개수가 N이고, 음수 사이클이 없을 때 최악의 상황을 고려하더라도 특정 두 노드의 최단 거리를 구성할 수 있는 에지의 최대 개수는 N-1이기 때문입니다. 모든 에지 E=(s,e,w)에서 다음 조건을 만족하면 업데이트를 실행합니다. 업데이트 반복 횟수가 K번이라면 해당 시점에 정답 리스트의 값은 시작점에서 K개의 에지를 사용했을 때 각 노드에 대한 최단 거리입니다.

• 업데이트 조건과 방법
• D[s] != ∞이며 D[e] > D[s] + w 일 때 D[e] = D[s] + w 로 리스트의 값을 업데이트한다.

음수 사이클이 없을 때 N-1번 에지 사용 횟수를 반복하면 출발 노드와 모든 노드 간의 최단 거리를 알려주는 정답 리스트가 완성됩니다. 이렇게 완성 후 마지막으로 이 그래프에 음수 사이클이 존재하는지 확인해야 합니다.

2-3. 음수 사이클 유무 확인하기

음수 사이클의 유무를 확인하기 위해 모든 에지를 한 번씩 다시 사용해 업데이트 되는 노드가 발생하는지 확인합니다. 만약 업데이트 되는 노드가 있다면 임수사이클이 있다는 뜻이 되고, 2단계에서 도출한 정답 리스트가 무의미하고 최던 거리를 찾을 수 없는 그래프라는 뜻이 됩니다. 음수 사이클이 존재하면 이 사이클을 무한하게 돌수록 가중치가 계속 감소하므로 최단 거리를 구할 수 없습니다.

실제 코테에서는 벨만-포드 알고리즘을 이용해 최단 거리를 구하는 문제보다 음수 사이클 판별 문제가 더 빈번하게 출제된다고 합니다.
따라서 마지막에 한 번 더 모든 에지를 사용해 업데이트 되는 노드가 있는지 확인해야 합니다.

BOJ 11657 타임머신

문제

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.

1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다.

출력

만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다. 그렇지 않다면 N-1개 줄에 걸쳐 각 줄에 1번 도시에서 출발해 2번 도시, 3번 도시, ..., N번 도시로 가는 가장 빠른 시간을 순서대로 출력한다. 만약 해당 도시로 가는 경로가 없다면 대신 -1을 출력한다.

입출력 예

풀이

import sys

# 입력을 빠르게 받기 위해 sys.stdin.readline 사용
input = sys.stdin.readline

# 도시의 개수 N과 버스 노선의 개수 M 입력
N, M = map(int, input().split())

# 버스 노선의 정보를 담을 리스트와 각 도시까지의 최단 거리를 담을 리스트 초기화
edges = []
distance = [sys.maxsize] * (N + 1)

# M개의 버스 노선 정보 입력 받기
for i in range(M):
    start, end, time = map(int, input().split())
    edges.append((start, end, time))

# 시작 도시(1)의 최단 거리를 0으로 초기화
distance[1] = 0

# N-1번의 루프를 통해 최단 거리 계산
for _ in range(N - 1):
    # 모든 버스 노선에 대해 확인
    for start, end, time in edges:
        # 조건에 맞으면 최단 거리 업데이트
        if distance[start] != sys.maxsize and distance[end] > distance[start] + time:
            distance[end] = distance[start] + time

mCycle = False
# 음수 사이클 확인
for start, end, time in edges:
    if distance[start] != sys.maxsize and distance[end] > distance[start] + time:
        mCycle = True

# 음수 사이클이 없으면 결과 출력
if not mCycle:
    for i in range(2, N + 1):
        if distance[i] != sys.maxsize:
            print(distance[i])  # 최단 거리 출력
        else:
            print(-1)  # 경로가 없는 경우 -1 출력
else:
    print(-1)  # 음수 사이클이 존재하는 경우 -1 출력