[동빈나]이코테 2021 강의 몰아보기 (17)(2021.1.21)

본 내용은 해당 강의 토대로 작성

벨만 포드 알고리즘

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

• 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)

음수 간선이 없을 경우

• 다익스트라 알고리즘으로 풀 수 있다.

음수 간선이 있을 경우

• 일반적인 경우에도 최단 거리를 구할 수 있다.
• 그러나, 음수 간선의 순환이 일어난다면 최단거리가 무한히 줄어들 수 있으므로 거리가 음의 무한인 노드가 발생한다.

음수 간선에 관하여 최단 경로 문제의 분류

1. 모든 간선이 양수인 경우
2. 음수 간선이 있는 경우
   1. 음수 간선 순환은 없는 경우
   2. 음수 간선 순환이 있는 경우

벨만 포드 최단 경로 알고리즘

• 음의 간선이 포함된 상황에서도 사용할 수 있다.
  • 음수 간선의 순환을 감지
  • 벨만 포드의 기본 시간 복잡도는 O(VE)로 다익스트라 알고리즘보다 느리다.

알고리즘 순서

1. 출발 노드를 설정
2. 최단 거리 테이블 초기화
3. 다음의 과정 N-1번 반복
   1. 전체 간선 E개를 하나씩 확인
   2. 각 간선을 거쳐, 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신
4. 만약 음수 간선 순환이 발생하는지 체크하고 싶다면, 3번의 과정을 한 번 더 수행
   • 이때 최단 거리 테이블이 갱신 된다면, 음수 간선 순환이 존재하는 것이다.

다익스트라 알고리즘과의 비교

다익스트라 알고리즘	벨만 포드 알고리즘
매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택	매번 모든 간선을 전부 다 확인, 다익스트라 알고리즘에서의 최적의 해를 항상 포함
음수 간선이 없다면, 최적의 해를 찾을 수 있다.	다익스트라 알고리즘에 비해서, 시간이 오래걸린다. 음수 간선 순환 감지 가능.

Python 소스코드

import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정

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

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

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

# 벨만 포드 알고리즘을 수행
negative_cycle = bf(1) # 1번 노드가 시작 노드

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