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

최초작성일 [2020.01.20]

벨만-포드 알고리즘

다익스트라 알고리즘은 서로 다른 두 정점 사이의 간선의 가중치가 0보다 크거나 같을 경우 최단 경로를 찾는 데 적절한 알고리즘이라면 벨만-포드(Bellman-Ford)알고리즘은 간선의 가중치가 음수일 때 최단 경로를 찾기 적절한 알고리즘이다.

벨만-포드 알고리즘은 출발 정점의 dist를 0으로 설정한 뒤, 그래프 내 모든 간선을 대상으로 relaxation을 수행한다. 이 relaxation은 출발 정점을 제외한 나머지 |V| - 1 번 수행하므로 시간복잡도는 O(|V| * |E|) 이다.

1. 출발 정점 A의 dist를 0으로, 나머지 정점의 dist는 무한대로 설정한다.

2. 모든 간선(총 9개)를 대상으로 relaxation을 수행한다. relaxation을 수행하는 간선의 순서는 상관없다.

3. 2번을 |V| - 1번 수행한다.

위 과정을 거치면 그림의 왼쪽에서 오른쪽으로 각 정점의 dist가 갱신되며, 각 dist는 출발 정점 A에서 각 정점으로 향하는 최단 거리를 나타낸다.

벨만-포드 알고리즘을 코드로 구현하면 아래와 같다.

def relax(v1, v2):
  if dist[v2] > dist[v1] + weight(v1, v2):
    dist[v2] = dist[v1] + weight(v1, v2)
    prev[v2] = v1


def Bellman-Ford(G, start):
  for u in V:
    dist[u] = infinity
    prev[u] = nil
    
  dist[start] = 0
  
  for _ in range(|V| - 1):  # O(|V|)
    for (v1, v2) in G:      # O(|E|)
      relax(v1, v2)

Negative Cycle

negative cycle이란 음수 가중치를 가지는 그래프의 사이클에 의해 두 정점의 거리가 음의 무한대로 계산되는 것을 말한다.

위 그림과 같이 그래프에서 negative cycle을 이루면 벨만-포드 알고리즘을 적용할 수 없다.

증

어떤 그래프에 negative cycle이 있지만 벨만-포드 알고리즘으로 최단거리를 구할 수 있다고 가정해보자. |V| - 1 번의 relaxation을 거치고나면 출발정점에서 각 정점으로의 최단거리가 구해지므로, |V|번째 relaxation을 했을 때 모든 정점의 dist는 갱신될 일이 없어야 한다.

|V|번째의 relaxation에서 정점 A, B, C의 dist가 갱신될 일이 없으려면 아래의 조건이 모두 참이어야 한다.

dist[A] <= dist[C] + weight(C, A)
dist[B] <= dist[A] + weight(A, B)
dist[C] <= dist[B] + weight(B, C)

위 조건들이 참이 되려면 weight(C, A), weight(A, B), weight(B, C)는 모두 0보다 같거나 큰, 음이 아닌 수여야 한다. 하지만 negative cycle을 이루는 A, B, C 사이의 간선에는 음의 가중치가 존재하므로 가정과 모순을 이룬다. 따라서 벨만-포드 알고리즘은 negative cycle을 이루는 그래프에서 최단 거리를 구할 수 없음을 증명한다.

‌

Negative Cycle 찾는 방법

1. |V|번째 relaxation에 dist가 갱신되는 모든 정점을 찾아서 큐에 저장한다. 이 정점들이 negative cycle에 있는 정점들이다.(negative cycle에 포함되지 않는 정점은 |V|번째 relaxtion에서 dist가 갱신될 일이 없다.)

2. 큐를 이용하여 BFS를 수행한다.

3. BFS를 수행하면서 큐에 있는 정점들과 인접한 다른 정점들을 탐색한다.

negative cycle을 찾는 방법은 무한차익거래(infinite arbitrage)를 찾아내는 알고리즘에도 활용할 수 있다.

출처

• 코세라 알고리즘 강의
• ratsgo.github.io - 벨만포드 알고리즘