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

그래프를 사용하는 최단거리 알고리즘 중 하나이다. 알고리즘은 배워도 배워도 끝이 없다. 하나 배우면 앞에 배운거 까먹고 ㅎㅎ.. 그래서 이렇게 기록을 해놔야 한다. 다익스트라 알고리즘이라는 많이들 사용하는 알고리즘이 있는데 왜 벨만-포드 알고리즘을 써야하는 경우가 생기는가?

-> 간선의 가중치가 음수가 포함된 경우에도 최단거리를 구할 수 있기 때문이다. 특히 가중치가 음수인 경우 간선을 거치면 거칠수록 최단거리가 점점 작아져 음의 무한대로 발산하는 경우가 생기는데, 벨만-포드 알고리즘을 통해 이러한 경우를 구별할 수 있다.

💡 어떤 원리인데?

기본적인 원리는 다익스트라 알고리즘과 같다. 다른점은 다익스트라 알고리즘은 하나의 정점을 기준으로 해당 정점에 연결된 간선들과 정점을 고려했다면 벨만-포드 알고리즘은 모든 정점을 돌면서 모든 간선을 고려해야 한다. 왜냐하면 가중치가 음수인 간선은 항상 최단거리를 줄일 여지가 있기 때문이다. 따라서 벨만-포드 알고리즘의 시간복잡도는 O(|V||E|)로 다익스트라 알고리즘보다는 느리다.

알고리즘	특징	시간복잡도
다익스트라	특정 노드에 대한 다른 노드까지의 최단거리, 가중치는 양수로만 이루어져야 함	O(|E|+|V|log |V|)
벨만-포드	특정 노드에 대한 다른 노드까지의 최단거리, 음수가 포함된 가중치까지 커버 가능	O(|V||E|)

💡 구현 코드

일반화한 벨만-포드 알고리즘 코드는 아니고 백준의 11657번 타임머신 코드이다. 그냥 벨만-포드를 정석적으로 사용하면 되는 문제라서 바로 올린다.

import sys
input = sys.stdin.readline

INF = 1e9

# 벨만 포드 알고리즘
def bf(start):
    # 시작 노드는 최단거리가 자기 자신이므로 0으로 줌
    dists[start] = 0
    # 값을 계속해서 갱신하기 때문에 N번 순회함
    # N-1번 순회해도 되는데 N번 순회하는 이유는 음수 간선이 사이클로 존재할 경우 최단 거리를 표시할 수 없는 경우가 발생하는지 여부를 판단하기 위함
    for i in range(N):
        # 모든 간선을 순회함
        for j in range(M):
            # 간선의 정보를 저장한 배열에서 현재 노드, 연결된 노드, 값을 가져옴
            cur_node = edges[j][0]
            next_node = edges[j][1]
            cost = edges[j][2]
            # cur_node를 거쳐서 next_node로 도달했을 때의 거리값이 최단거리 배열에 기록된 거리값보다 작으면 값을 갱신해줌
            if dists[cur_node]!=INF and dists[next_node] > dists[cur_node] + cost:
                dists[next_node] = dists[cur_node] + cost
                # 이미 N-1번 순회해서 값의 갱신이 더이상 일어나지 않아야 하는데 갱신이 일어난다는 것은 음수 간선에 의한 순환이 일어난다는 것임
                if i==N-1:
                    return True
    return False

# 노드의 개수 N, 간선의 개수 M
N, M = map(int, input().split())

# 간선의 정보를 저장할 배열
edges = []

# 1번 노드로부터의 최단 거리를 저장할 배열
dists = [INF] * (N+1)

# 간선의 정보를 입력받음 각 정보는 A노드에서 B노드로 갈 때 C의 값을 가짐
for _ in range(M):
    A, B, C = map(int, input().split())
    edges.append((A, B, C))

isCycle = bf(1)

if isCycle == True:
    print(-1)
else:
    for i in range(2, N+1):
        if dists[i] == INF:
            print(-1)
        else:
            print(dists[i])