[알고리즘 이론] 벨만-포드 알고리즘

그래프 최단 경로 알고리즘은 크게

1. 플로이드워셜
2. 다익스트라
3. 벨만-포드

가 있다. 여기서 벨만-포드 알고리즘에 대해서 알아보고자 한다.

 

기능과 특징

벨만-포드 알고리즘은

• 다익스트라 알고리즘처럼 하나의 출발 노드에서 다른 모든 노드까지의 최단 경로를 구하는 알고리즘이다.
• 하지만 다익스트라 알고리즘과 가장 큰 차이는, 가중치가 음수인 간선이 있어도 최단 경로를 구할 수 있다는 점이다.
• 또한 음수 사이클이 존재하는지도 탐지할 수 있다는 특징이 있다.
• 시간 복잡도는 O(VE)이다. (V : 노드의 수,  E : 엣지의 수)

 

동작 원리

1. 엣지 리스트로 그래프를 구현하고 최단 경로 리스트 초기화하기

초기화 단계로, 벨만-포드 알고리즘은 엣지 중심으로 동작하기 때문에 그래프를 엣지 리스트로 구현한다. 또한 최단 경로 리스트는 출발 노드는 0, 나머지 노드는 무한대로 초기화한다.

2. 모든 엣지를 확인해 최단 거리 리스트 업데이트하기

최단 거리 리스트에서 업데이트를 반복하는 최대 횟수는 노드 개수 N에서 1을 뺀 N−1번이다. 이는 음수 사이클이 없는 경우, 어떤 노드로 가는 최단 경로를 구성하는 간선(Edge)의 최대 개수가 N−1개이기 때문이다. 노드가 N개 있을 때, 최단 경로를 구성하는 간선이 N−1개를 초과하면 경로상에 사이클이 생기게 되는데, 최단 경로는 사이클을 포함할 수 없으므로 간선 개수는 최대 N−1개를 넘을 수 없다.

 

모든 Edge E=(s, e, w)에서 다음 조건을 만족하면 업데이트를 실행한다.

dist[s] != ∞ 이며 dist[e] > dist[s] + w일 때, dist[e] = dist[s] + w 로 업데이트

 

업데이트 반복 횟수가 K번이라면 해당 시점에 정답 리스트의 값은 시작점에서 K개의 엣지를 사용했을 때 각 노드에 대한 최단 거리이다. 음수 사이클이 없을 때 N-1번 Edge 사용 횟수를 반복하면 출발 노드와 모든 노드 간의 최단 거리를 알려 주는 정답 리스트가 완성된다.

3. 음수 사이클 유무 

최단 거리를 구한 뒤, 그래프에 음수 사이클이 존재하는지 확인하기 위해 모든 간선을 한 번 더 검사해야 한다. 이를 위해 N−1번의 반복 이후 모든 간선을 다시 순회하여, 추가로 최단 거리 업데이트가 발생하는지 확인한다. 만약 업데이트가 발생한다면, 이는 음수 사이클이 존재한다는 의미이며, 이 경우 2단계에서 도출한 최단 거리 결과는 의미가 없어진다. 음수 사이클이 존재하면 사이클을 계속 순회하면서 최단 거리가 무한히 갱신되기 때문이다.