[이코테_코딩테스트] 벨만 포드 알고리즘 (Bellman-Ford Algorithm)

date

Aug 19, 2023

slug

coding-test-bellman-ford-algorithm

author

status

Public

음수 간선이 포함된 상황에서의 최단 거리 문제

[예시] BOJ ‘타임머신‘

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

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다.

각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다.

시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.

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

도시의 개수 : N (1 ≤ N ≤ 500)

버스 노선의 개수 : M (1 ≤ M ≤ 6,000)

모든 간선의 비용이 양수인 경우

다익스트라 최단 경로 알고리즘을 사용하면 된다.

https://morethan-dogeon.vercel.app/coding-test-shortest-path-2

음수 간선이 포함된 경우

여전히 최단 거리를 계산할 수 있다.

단순히 음수 간선이 있다고 해서 최소 비용을 결정 못하는 것이 아님

음수 간선의 순환이 포함된 경우

최단 거리가 음의 무한인 노드가 발생한다.

벨만 포드 최단 경로 알고리즘 (Bellman-Ford Algorithm)

음수 간선에 관한 최단 경로 문제는 다음과 같이 분류할 수 있다.

모든 간선이 양수인 경우

음수 간선이 있는 경우

음수 간선 순환은 없는 경우
음수 간선 순환이 있는 경우

벨만 포드 최단 경로 알고리즘은 음의 간선이 포함된 상황에서도 사용할 수 있다.

음수 간선의 순환을 감지할 수 있다.
기본 시간 복잡도는 로 다익스트라 알고리즘에 비해 느리다.

동작 과정

출발 노드 설정

최단 거리 테이블 초기화

다음의 과정 N - 1번 반복

전체 간선 E개를 하나씩 확인한다.
각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.

만약 음수 간선 순환이 발생하는지 체크하고 싶다면 3번의 과정을 한 번 더 수행한다.

이때 최단 거리 테이블이 갱신되면 음수 간선 순환이 존재하는 것이다.

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

다익스트라 알고리즘

매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
음수 간선이 없다면 최적의 해를 찾을 수 있다.

벨만 포드 알고리즘

매번 모든 간선을 전부 확인한다.

다익스트라 알고리즘에서의 최적의 해를 항상 포함한다.

다익스트라 알고리즘에 비해 시간이 오래 걸리지만 음수 간선 순환을 탐지할 수 있다.

벨만 포드 알고리즘 코드 예시 (Python)


import sys
input = sys.stdin.readline
INF = int(1e9)

def bf(start):
    # 시작 노드 초기화
    dist[start] = 0
    # n번의 round 반복
    for i in range(n):
        # 매번 모든 간선 확인
        for j in ranage(m):
            cur = edges[j][0]
            next_node = edges[j][1]
            cost = edges[j][2]
            # 현재 간선을 거쳐 다른 노드를 이동하는 거리가 더 짧은 경우
            if dist[cur] != INF and disg[next_node] > dist[cur] + cost:
                dist[next_node] = dist[cur] + cost
                # n번째 라운드에서도 값이 갱신된다면 -> 음수 순환 존재
                if i == n - 1:
                    return True
    return False

# 노드의 개수, 간선의 개수 입력
n, m = map(int, input().split())
# 모든 간선에 대한 정보 담는 리스트
edges = []
# 최단 거리 테이블 무한 값으로 초기화
dist = [INF] * (n + 1)

# 간선 정보 입력
for _ in range(m):
    a, b, c = map(int, input().split())
    # a번 노드에서 b번 노드로 가는 비용이 c
    edges.append((a, b, c))

# 벨만 포드 알고리즘 수행
negative_cycle = bf(1)

if negative_cycle:
    print("-1")
else:
    # 1번 노드 제외한 다른 모든 노드로 가기 위한 최단 거리 출력
    for i in range(2, n + 1):
        # 도달할 수 없는 경우 -1 출력
        if dist[i] == INF:
            print("-1")
        # 도달할 수 있는 경우 거리 출력
        else:
            print(dist[i])

이 글은 유튜브 “동빈나” 채널의 “코딩 테스트를 위한 벨만 포드 알고리즘 7분 핵심 요약” 영상을 보고 작성하였습니다.