최단경로 - (2) 벨만-포드(Bellman-Ford) 알고리즘

벨만-포드 알고리즘

벨만-포드 알고리즘은 앞서 살펴본 다익스트라 알고리즘과 같이 그래프에서 시작 점점으로부터 다른 모든 정점까지의 최단 경로를 찾기 위한 알고리즘이다. 하지만 중요한 차이점이 있는데, 벨만-포드 알고리즘은 그래프 내에 음수 가중치를 갖는 간선이 있는 경우에도 활용할 수 있으며 경로 중에 음수 사이클이 존재하는 경우를 피해 최단 거리를 계산할 수 있다는 것이다.

그래프에 음수 사이클이 존재한다고 가정해보자. 다익스트라 알고리즘에서는 시작 정점에서 목표 정점에 도달하기까지 인접 간선들을 탐색하면서 최소 비용을 찾을 때 마다 거리 값을 갱신해 나간다. 그런데 이 과정에서 음수 사이클을 만난다면 사이클을 돌수록 비용이 줄어든다고 판단할 것이고, 사이클 안에서 계속해서 맴돌다가 결국 도달할 수 없는 정점이 발생하게 된다. 따라서 이런 그래프에서는 출발점으로부터 도달가능하되, 음수 사이클이 없는 최단 경로를 구해야한다.

벨만-포드 알고리즘 구현

그렇다면 어떻게 음수 사이클 안에서 무한 뺑뺑이 도는 경우를 피할 수 있을까? 방법은 그래프의 정점의 개수를 $V$라고 할 때, 인접 간선을 검사하고 거리 값을 갱신하는 과정을 $V-1$번으로 제한하는 것이다. 그래프에서 시작 정점에서 특정 정점까지 도달하기 위해 거쳐가는 최대 간선 수는 $V-1$개 이기 때문이다. 따라서 경로에 $V$번째 간선이 추가되는 순간 사이클에 진입했다고 판단할 수 있다.

벨만-포드 알고리즘 프로세스

1. 시작 정점을 결정한다.
2. 시작 정점부터 다른 정점까지 거리 값 모두 무한대로 초기화한다. (시작 정점은 0으로 초기화)
3. 현재 정점의 모든 인접 정점들을 탐생하며, 기존에 기록된 인접 정점까지의 거리보다 현재 정점을 거쳐 인접 정점에 도달하는 거리가 더 짧다면 인접 정점까지의 거리를 갱신한다.
4. 3번 과정을 $V-1$번 반복한다.
5. 위 과정을 모두 마친 후에도 거리가 갱신되는 경우가 있다면 그래프에 음수 사이클이 존재한다는 것을 알 수 있다.
   
   

벨만-포드 알고리즘 코드 (Python)

def bellman_ford(graph, start):
    distance, predecessor = dict(), dict()  # 거리 값, 각 정점의 이전 정점을 저장할 딕셔너리
    # 거리 값을 모두 무한대로 초기화 / 이전 정점은 None으로 초기화
    for node in graph:  
        distance[node], predecessor[node] = float('inf'), None
    distance[start] = 0  # 시작 정점 거리는 0

    # 간선 개수(V-1)만큼 반복
    for _ in range(len(graph) - 1):
        for node in graph:
            for neighbour in graph[node]:  # 각 정점마다 모든 인접 정점들을 탐색
                # (기존 인접 정점까지의 거리 > 기존 현재 정점까지 거리 + 현재 정점부터 인접 정점까지 거리)인 경우 갱신
                if distance[neighbour] > distance[node] + graph[node][neighbour]:
                    distance[neighbour] = distance[node] + graph[node][neighbour]
                    predecessor[neighbour] = node

    # 음수 사이클 존재 여부 검사 : V-1번 반복 이후에도 갱신할 거리 값이 존재한다면 음수 사이클 존재
    for node in graph:
        for neighbour in graph[node]:
            if distance[neighbour] > distance[node] + graph[node][neighbour]:
                return -1, "그래프에 음수 사이클이 존재합니다."

    return distance, predecessor
    
    
# 음수 사이클이 존재하지 않는 그래프
graph = {
    'A': {'B': -1, 'C':  4},
    'B': {'C':  3, 'D':  2, 'E':  2},
    'C': {},
    'D': {'B':  1, 'C':  5},
    'E': {'D': -3}
}

# 그래프 정보와 시작 정점을 넘김
distance, predecessor = bellman_ford(graph, start='A')

print(distance)
print(predecessor)


# 음수 사이클이 존재하는 그래프
graph = {
    'A': {'B': -1, 'C':  4},
    'B': {'C':  3, 'D':  2, 'E':  2},
    'C': {'A': -5},
    'D': {'B':  1, 'C':  5},
    'E': {'D': -3}
}


distance, predecessor = bellman_ford(graph, start='A')

print(distance)
print(predecessor)

시간 복잡도

$V-1$번 인접한 모든 간선들을 검사하는 과정을 거치기 때문에 벨만-포드 알고리즘의 시간 복잡도는 $O(VE)$가 된다. 시간 복잡도가 $O(ElogE)$였던 다익스트라 알고리즘에 비해서 복잡도가 더 크기는 하지만, 그래프에 음수 간선이 존재할 때 사용할 수 있다는 점, 음수 사이클 존재 여부를 판별할 수 있다는 점에서 유용하게 활용할 수 있는 알고리즘이다.