소개

벨만-포드 알고리즘은 그래프상의 한 정점에서 출발점으로 하여 다른 모든 정점에 대해서 최단 경로를 찾는 알고리즘이다. 최단 경로를 찾는 또 다른 알고리즘인 다익스트라와 달리 벨만-포드 알고리즘은 음수 간선을 지닌 그래프에서도 동작한다. 벨만-포드 알고리즘은 그래프의 정점이 개이면 출발점에서 다른 정점들로 가는 모든 단순 경로(한 번 방문한 정점을 다시 방문하지 않는 경로) 중 어느 것도 개보다 더 많은 간선을 거칠 수 없음을 이용한다.

원리

정점의 개수가 인 그래프에서 시작점 에 대하여 최단 거리표 을 다음과 같이 정의하자.

시작점에서 출발해 간선을 개 이하로 거쳐 정점 로 가는 최소 경로의 길이

만약 그러한 경로가 없을 경우에는 무한대로 간주한다. 은 만 0으로 초기화하고 나머지 셀은 전부 무한으로 초기화한다. 를 안다고 가정하자. 이를 바탕으로 를 구할 수 있을까? 는 의 경로에서 간선을 한 번 더 지날 수 있게 된 것으로 해석할 수 있다.

다이어그램을 그리는 중..

만약 정점 에서 정점 로 가는 간선의 가중치가 이고 라면 (즉 가 함유하는 방법으로 정점 로 간 뒤 가중치가 인 간선을 통해 정점 로 가는 방법이 기존의 의 방법보다 거리가 짧다면) 를 로 결정할 수 있을 것이다. 이러한 방식으로 으로부터 을 구하고, 로부터 을 구하며, 재귀적으로 을 구할 수 있다. 은 개 이하의 간선을 거쳐 갈 때의 최단 거리이므로 우리가 구하고자 하는 궁극적인 최단 거리표가 될 것이다.

예시로 이해해보자. 다음과 같은 그래프에 시작점 정점 가 있다고 가정하자.

다이어그램을 그리는 중..

을 바탕으로 을 구해보자. 정점 에서부터 간선을 딱 한 개 거쳐 이동할 수 있는 정점는 와 가 있으므로 이를 갱신해 줄 수 있다.

을 바탕으로 을 구해보자. 의 방법으로 정점 로 간 뒤 간선을 하나 더 거치면 정점 로 갈 수 있으므로 이를 갱신해준다. 의 방법으로 정점 로 간 뒤 간선을 하나 더 거쳐 정점 로 가는 방법은 의 방법으로 정점 로 가는 방법보다 짧다. 따라서 이다.

을 바탕으로 을 구해보자. 앞서 계산한 보다 이 더 짧으므로 이다.

이렇게 해서 완성한 은 이 그래프의 궁극적인 최단 거리표이다.

음수 사이클

음수 가중치 그래프에서 최단 경로를 계산할 때의 주의할 점은 해당 그래프가 음수 사이클을 가지고 있을 수 있다는 것이다. 음수 사이클이란 어떠한 한 정점에서 다른 정점을 거쳐 다시 돌아왔을 때 비용이 더 적어지는 경로를 말한다. 다음은 음수 사이클의 한 예이다.

다이어그램을 그리는 중..

정점 에서 를 거친 후 다시 로 오면 총 비용이 1만큼 줄어있다. 이 행위를 무한히 반복하면 총 비용을 음의 무한대로 발산시킬 수 있다. 이 상황에서 정점 에서 로 가는 최단 경로를 계산해 볼 수 있는가? 결국 이 그래프에서 최단 거리를 재는 것은 무의미하다. 우리가 벨만-포드 알고리즘을 사용하여 계산한 최단 거리도 음수 사이클을 감지하지 못하면 사실은 유효하지 않을 수 있다. (위 그래프를 상대로 벨만-포드 알고리즘을 수행해보라. 적어도 음의 무한대를 표현해 주지는 못한다.) 그러므로 벨만-포드를 사용할 때는 음수 사이클을 감지해 주는 과정이 필수이다.

음수 사이클의 감지는 의외로 간단하다. 을 구한 뒤 과 비교해 갱신이 일어났는지를 검사하면 된다. 만약 그래프가 음수 사이클을 가지고 있지 않다면 은 최단 거리 문제에 대한 이 그래프에서의 최적해이므로 최단 거리를 아무리 갱신해도 변화가 일어나지 않을 것이다. 그래프가 음수 사이클을 가지고 있다면 은 이 그래프에서의 최적해가 아니며 최단 거리가 무한히 갱신될 것이다.

구현

벨만-포드 알고리즘을 위해서는 그래프를 인접 리스트로 표현하는 것이 좋다. 왜냐하면 그래프의 간선을 기준으로 반복문을 설계할 것이기 때문이다. 먼저 를 만들고, 을 만들기까지의 번의 단계와 음수 사이클을 판정하기 위한 1번의 단계를 합하여 총 번의 단계동안 모든 간선을 검사해 최단 거리표를 갱신해주면 된다.

INF = 1_000_000_000


# edge는 인접 리스트이다.
# edge[n]은 정점 n에서 뻗어나온 모든 간선의 정보를 담은 리스트이다.
# 각 간선은 (다음 정점 번호, 간선의 가중치)의 형태로 표현한다.
def bellman_ford(edge: list[list[tuple[int, int]]], start_node: int) -> list[int]:
    result = [INF] * len(edge)
    result[start_node] = 0
    for step in range(len(edge)):
        for node in range(len(edge)):
            for next_node, cost in edge[node]:
                if result[next_node] > result[node] + cost:
                    result[next_node] = result[node] + cost
                    # 음수 사이클 판정
                    if step == len(edge) - 1:
                        raise Exception("음수 사이클 감지됨")
    return result

정점이 개라고 하면 번의 단계마다 개의 모든 간선을 확인하므로 총 시간복잡도는 이다.