[Algorithm] 벨만-포드 (Bellman-Ford) 알고리즘

Bellman-Ford

Idea

벨만-포드 알고리즘은 한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘입니다. 이때, 다익스트라와 달리 간선의 가중치가 음수인 경우에도 최단 거리를 구할 수 있습니다. 

단, 음의 사이클이 없는 그래프에서만 벨만-포드 알고리즘을 적용할 수 있습니다. 이를 위해 한 노드에서 다른 노드까지의 최단 경로를 많아봐야 V-1개의 간선을 지난다는 가정을 세웁니다.

경로 계산 방식에는 아래와 같은 종류가 있습니다.

1. (One-To-One) 한 지점에서 다른 특정 지점까지의 최단경로 구하기
2. (One-To-All) 한 지점에서 다른 모든 지점까지의 최단경로 구하기
3. (All-To-All) 모든 지점에서 모든 지점까지의 최단경로 구하기

벨만-포드 알고리즘은 이 중 2번째 유형(One-To-One) 입니다.

다익스트라는 벨만-포드보다 빠르지만 음수의 가중치가 있는 그래프에서는 사용할 수 없습니다.

따라서 양수의 가중치만 있는 그래프에서는 다익스트라를, 음수의 가중치가 있다면 벨만-포드 알고리즘을 사용해야 합니다.

또한, 벨만 포드 알고리즘을 통해서 음의 사이클 존재 여부를 파악할 수 있습니다! (V-1개의 간선보다 더 많은 간선을 통해 최단 경로를 구하는 경우, 음의 사이클이 존재한다.)

 

 

다익스트라 알고리즘과 차이점

다익스트라 알고리즘에서는 매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택해서 1단계씩 최단 거리를 구해갑니다.

하지만 벨만-포드 알고리즘에서는, 매 단계마다 모든 간선을 전부 확인하면서 모든 노드 간의 최단 거리를 구해갑니다.

즉, 다익스트라는 방문하지 않은 노드 중에서 최단 거리가 가장 가까운 노드만을 방문하는 반면, 벨만-포드는 매 단계마다 모든 노드를 방문하는 것입니다.

따라서 음의 가중치를 가지는 간선이 있더라도 최적의 해를 구할 수 있으며, 다익스트라보다는 시간이 더 오래 걸립니다.

 

동작 과정

1. 출발 노드를 설정한다.
2. 최단 거리 테이블을 초기화한다.
3. 다음의 과정을 (V(=정점) - 1)번 반복한다.
   1. 모든 간선 E개를 하나씩 확인한다.
   2. 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.

• 만약 음수 간선 순환이 발생하는지 체크하고 싶다면 3번 과정을 한 번 더 수행한다.
  --> 이때 최단 거리 테이블이 갱신된다면 음수 간선 순환이 존재하는 것이다.

위 그래프에서 1번 노드를 출발지로 설정하고 나머지 모든 노드에 대한 최단 경로를 구하는 동작을 살펴보겠습니다.

[Iteration 1]

처음 iteration은 출발 노드인 1번 노드에 대해 시작합니다.

각 간선을 탐색하는 순서는 상관이 없으나, 한 간선에 대해 dist 값이 INF가 아닌 정점이 연결된 경우에만 해당 간선을 탐색하여야 합니다. (즉, 도달할 수 있는 정점이 연결된 간선에 대해서만 탐색)

1번 노드에서 나가는 3개의 간선에 의해 dist[2], dist[3], dist[4]가 갱신되었습니다.

2번 노드에서 나가는 간선에 의해 dist[5]가 7로 갱신되었고, dist[3]은 유지되었습니다.

3번 노드에서 나가는 간선들에 의해 dist[5]가 6으로 갱신되었다. (3 + 6 - 3) dist[4]는 유지되었습니다.

4번 노드에서 나가는 간선들에 의해, dist[2]와 dist[5]가 갱신되었습니다.

[Iteration 2]

이후의 Iteration에서는, 다른 노드를 순서대로 시작점으로 두고 최단거리를 갱신합니다.

 

음의 사이클

빨간색으로 칠해진 사이클 속 가중치의 합은 총 -1입니다. 따라서, 해당 사이클을 거치는 경로에서 사이클을 반복할 수록 경로의 거리는 작아지게 됩니다. 

벨만 포드 알고리즘은 한 노드에서 다른 노드까지의 최단 경로를 많아봐야 V-1개의 간선을 지난다는 가정을 세웁니다.
이것의 의미는, 최단 경로가 V-1개보다 많은 간선을 지나게 된다면 음의 사이클이 존재한다는 의미입니다.

 

Code

import sys
input = sys.stdin.readline

INF = int(1e9) # 무한대 값

# 노드, 간선의 개수 입력
v, e = map(int, input().split())
# 모든 간선에 대한 정보를 담는 리스트
edges = []

# 최단거리 테이블을 무한대로 초기화
distance = [INF] * (v + 1)

# 모든 간선의 정보 입력
for _ in range(e):
    sv, ev, cost = map(int, input().split())
    edges.append((sv, ev, cost))

# 벨만-포드 알고리즘
def bellmanFord(start):
    # 시작 노드에 대해서 초기화
    distance[start] = 0
    # v번 edge relaxation을 반복.
    # v - 1번 탐색하고 마지막 한번은 Negative cycle 존재 확인
    for i in range(v):
        # 매 반복마다 모든 간선을 확인하며 갱신
        for j in range(e):
            curNode, nextNode, edgeCost = edges[j]
            # 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
            if distance[curNode] != INF and distance[curNode] + edgeCost < distance[nextNode]:
                distance[nextNode] = distance[curNode] + edgeCost
                # v번째 반복에서 갱신되는 값이 있으면 Negative cycle 존재
                if i == v - 1:
                    return False

    # 벨만-포드 정상종료
    return True

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

 

 

Time Complexity

초기화 작업

• O(V)

탐색 도중 더 짧은 경로를 발견하게 되면 d[v]와 π[v] 값을 갱신해주는 연산 (Relaxation)

• Relaxation 연산의 시간 복잡도는 O(1)이고 총 E회 수행하기 때문에 매 차례마다 O(E)의 시간이 소요되고 총 V−1 회의 차례를 수행하게 됩니다. 그러므로 총 O((V−1)E)=O(VE)의 시간이 걸립니다.

음의 가중치 사이클 검사

• O(E)

그러므로 벨만-포드 알고리즘의 시간 복잡도는 O(V+VE+E)=O(VE)입니다.