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

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 사용해보면서 배운 점을 정리한 글입니다.

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

한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘이다. 다익스트라 알고리즘이 모든 가중치가 양수인 경우에만 사용할 수 있는 반면에 벨만-포드 알고리즘은 노드 간의 간선 가중치가 음수인 경우에도 사용할 수 있다. 다만 시간 복잡도는 벨만-포드가 더 크기 때문에 가중치가 모두 양수라면 굳이 벨만-포드를 사용할 필요가 없다.

음수 사이클이 문제가 되는 이유

• 단순 음수 간선일 경우 : 단순 경로이므로 그대로 가중치를 계산하면 된다.
• 사이클이 존재하나 양수값이 더 클 경우 : 사이클을 순환하여도 이득이 없으므로 그대로 진행한다.
• 사이클이 존재하고 음수값이 더 클 경우 : 사이클을 순환할 수록 가중치가 감소해 최소 비용을 찾는 입장에서 사이클을 무한히 순환하고 목적지에 도착함은 실질적인 최단 경로라 보기 어렵다. 적어도 동일 노드를 방문하면 안된다는 등 제약 조건이 있어야 할 것이다.

최단 거리는 순화뇌어서는 안된다는 가정을 담고 있으므로 경로(Edge) 길이는 $|V| - 1$이 된다.

벨만-포드 알고리즘의 동작

1. 시작 노드를 설정한다.
2. 시작 노드에서 각 다른 노드의 거리 값을 무한대로 설정하고 시작 노드를 0으로 설정한다.
3. 현재 노드의 모든 인접 노드를 탐색하며 기존에 저장된 인접 노드까지의 거리보다 현재 노드를 거치고 인접 노드에 도달하는 게 더 짧을 경우 값을 갱신한다.
4. 3의 과정을 모든 노드에 대해 수행한다.
5. 모든 노드에 3 - 4를 수행하고서 또 거리가 갱신된다면 $-\infty$를 발생시키는 음수 사이클이 존재함을 의미한다.

위 그래프는 음수 사이클이 존재하지만 일단 벨만-포드 알고리즘을 적용하여 최단 거리 구하는 과정을 살펴보자. 시작점은 s라 한다.

우선 시작 노드를 0으로 초기화하고 나머지 노드에 대해 $\infty$으로 설정한다.

s의 인접노드는 a, c, e로 각각 3, 5, 2로 저장한다. (INF보다 작기 때문)

s의 인접노드를 모두 탐색했으니 a노드를 현재 노드로 옮긴다. a의 인접노드는 b노드 뿐으로 -1 < INF이므로 -1이 된다.

b 노드의 인접 노드는 g 노드 뿐으로 $-1 + 4 < INF$이기에 3으로 설정한다.

c 노드의 인접 노드는 d 뿐이고 c에서 d로 가는 최단 경로는 $11 < INF$이므로 11이 된다.

d 노드의 인접 노드는 g로 $11 + 8 > 3$으로 그대로 3을 유지한다.

e 노드의 인접 노드는 f이고 $INF > 5$이므로 f에 5를 저장한다.

f의 인접 노드는 e와 g로 e의 경우 $5-6 < 2$로 e를 -1로 갱신하고 g는 $5 + 7 > 3$으로 3을 유지한다. g의 인접 노드는 없으니 첫 번째 탐색을 종료한다. 이후 노드 개수 - 1만큼 반복하면 된다.

이로써 V - 1 개의 노드에 대해 모두 탐색을 종료했다. 그런데 그래프에서 볼 수 있듯이 e와 f 사이엔 음수 사이클이 존재하여 해당 사이클을 무한히 순회하면 모든 노드에 대해 $-\infty$가 될 수 있다. 따라서 위 과정처럼 동일 노드를 방문하지 않는다는 제약조건이 없다면 그대로 -1 등을 출력하여 경로가 존재할 수 없음을 표현해야 한다.

음수 사이클의 존재 여부 검출은 간단하다 V - 1번만큼 탐색을 마쳤으므로 최단 거리 제약 한계에 도달했다. 이 다음 순회에서도 만약 갱신되는 값이 존재한다면 앞으로도 계속 갱신됨을 의미하므로 음수 사이클이 존재함을 의미한다.

벨만-포드 알고리즘의 시간 복잡도

우선 $|V| - 1$번만큼 순회하므로 $O(V)$가 되고 매번 총 edge($O(E)$)만큼 탐색하므로 $O(|V||E|)$가 된다. 그런데 desne graph라면 E는 $V^2$에 근사해지므로 최악의 경우 $O(V^3)$이 된다. 이는 다익스트라 알고리즘이 최악의 경우 $O(V^2)$인 것과 비교했을 때 불리함을 알 수 있다. 따라서 벨만-포드 알고리즘은 간선의 가중치에 음수가 존재할 경우에만 채택해야 한다. 일종의 음수 가중치 지원에 대한 trade off 정도로 생각해야겠다.

python 코드

INF = float('inf')
V, E = map(int, input().split())
edges = []
for _ in range(E):
    s, d, w = map(int, input().split())
    edges.append((s, d, w))
def bellman-ford(start):
    dist = [INF] * (V + 1)
    dist[start] = 0
    for i in range(V):
        for s, d, w in edges:
            if dist[s] != INF and dist[d] > dist[s] + w:
                if i == V - 1:
                    return -1
                dist[d] = dist[s] + w
    return dist    

print(bellman-ford(0))