단일 출발지 최단 경로 문제
단일 출발지 최단 경로 문제는 방향성 가중치 그래프에서 주어진 출발 정점에서 다른 모든 정점까지의 최단 경로를 찾는 문제다. 이 문제에는 여러 변형이 존재한다. 간선에 음수 값이 허용되는지, 사이클이 존재하는지, 특정 정점 쌍 사이의 경로를 찾는지 등에 따라 문제가 달라진다.
벨만-포드 알고리즘
벨만-포드 최단 경로 알고리즘은 주어진 시작 정점 s에서 음수 가중치를 포함할 수 있는 방향 그래프의 모든 정점까지의 최단 경로를 찾는다. 알고리즘은 그래프의 모든 간선에 대해 반복적으로 작업을 수행하며, 현재까지 알려진 최단 경로 가중치를 업데이트하는 과정을 거친다. 이때, 경로는 그래프에 존재하는 정점 수를 초과할 수 없으므로, 모든 간선에 대해 |V|-1번 반복하면 충분히 모든 가능한 경로를 비교할 수 있다.
각 단계에서, 각 정점 v에 대해 현재까지 알려진 최단 경로 s~>v의 가중치를 저장한다. 시작 정점 s의 값은 0으로 유지하고, 나머지 정점의 값은 초기에 ∞로 설정한다. 그런 다음, 각 간선 e = (u, v)(여기서 u는 방향 간선의 출발 정점, v는 도착 정점)에 대해 다음 조건을 적용하여 값을 "완화"한다:
if weights[v] > weights[u] + e.weight {
weights[v] = weights[u] + e.weight
}벨만-포드 알고리즘은 기본적으로 최단 경로의 길이만 계산하지만, 선택적으로 시작 정점에서 각 정점까지의 최단 경로에서 이전 정점을 기억하는 구조를 유지할 수 있다. 이 구조를 통해 도착 정점에서 시작 정점까지의 경로를 재구성할 수 있다. 이는 위의 if 문 내부에 다음 구문을 추가하여 구현한다:
predecessors[v] = u예제
다음의 가중치 방향 그래프를 살펴보자:
정점 s에서 시작하는 최단 경로를 계산해 보자. 먼저 weights와 predecessors 구조를 다음과 같이 준비한다:
| weights | predecessors |
|---|---|
weights[s] = 0 |
predecessors[s] = 1 |
weights[t] = ∞ |
predecessors[t] = ø |
weights[x] = ∞ |
predecessors[x] = ø |
weights[y] = ∞ |
predecessors[y] = ø |
weights[z] = ∞ |
predecessors[z] = ø |
각 이완(relaxation) 반복 후의 상태를 보자. 각 반복은 모든 간선을 한 번씩 처리하며, 이 그래프에서는 총 4번의 반복이 수행된다.
1차 반복:
| 가중치 | 선행 노드 |
|---|---|
weights[s] = 0 |
predecessors[s] = s |
weights[t] = 6 |
predecessors[t] = s |
weights[x] = 4 |
predecessors[x] = y |
weights[y] = 7 |
predecessors[y] = s |
weights[z] = 2 |
predecessors[z] = t |
2차 반복:
| 가중치 | 이전 노드 |
|---|---|
weights[s] = 0 |
predecessors[s] = s |
weights[t] = 2 |
predecessors[t] = x |
weights[x] = 4 |
predecessors[x] = y |
weights[y] = 7 |
predecessors[y] = s |
weights[z] = 2 |
predecessors[z] = t |
3차 반복
| 가중치 | 이전 노드 |
|---|---|
weights[s] = 0 |
predecessors[s] = s |
weights[t] = 2 |
predecessors[t] = x |
weights[x] = 4 |
predecessors[x] = y |
weights[y] = 7 |
predecessors[y] = s |
weights[z] = -2 |
predecessors[z] = t |
반복 4:
| 가중치 | 이전 노드 |
|---|---|
weights[s] = 0 |
predecessors[s] = s |
weights[t] = 2 |
predecessors[t] = x |
weights[x] = 4 |
predecessors[x] = y |
weights[y] = 7 |
predecessors[y] = s |
weights[z] = -2 |
predecessors[z] = t |
음수 가중치 사이클
이 솔루션 구조의 또 다른 유용한 특성은 그래프에 음수 가중치 사이클이 존재하는지, 그리고 해당 사이클이 시작 정점에서 도달 가능한지 여부를 확인할 수 있다는 점이다. 음수 가중치 사이클은 간선 가중치의 합이 음수인 사이클을 의미한다. 이는 특정 시작 정점에서의 최단 경로가 잘 정의되지 않음을 나타내는데, 사이클을 반복해서 들어가면 경로의 가중치를 -∞로 계속 줄일 수 있기 때문이다. 경로를 완전히 완화한 후, 각 간선 e = (u, v)에 대해 v까지의 최단 경로 가중치가 u까지의 경로 가중치에 간선의 가중치를 더한 값보다 큰지 확인하면, 해당 간선이 음수 가중치를 가지고 있어 최단 경로의 가중치를 더 줄일 수 있음을 알 수 있다. 이미 충분한 횟수로 완화를 수행했으므로, 이 추가적인 가중치 감소가 무한히 계속될 것이라고 안전하게 가정할 수 있다.
예제
이 예제에서는 a에서 시작하는 최단 경로를 계산해 본다:
a->t->s->a 사이클의 총 간선 가중치는 -9이다. 따라서 a>>t와 as의 최단 경로는 정의되지 않는다. a~>b 또한 b->t->s가 음수 가중치 사이클이기 때문에 정의되지 않는다.
이것은 relaxation 루프를 실행하고, 위에서 언급한 모든 간선을 확인한 후에 확인된다. 이 그래프에서 relaxation을 수행한 후의 결과는 다음과 같다:
| weights |
|---|
weights[a] = -5 |
weights[b] = -5 |
weights[s] = -18 |
weights[t] = -3 |
이후 수행할 간선 확인 중 하나는 다음과 같다:
e = (s, a)
e.weight = 4
weight[a] > weight[s] + e.weight => -5 > -18 + 4 => -5 > -14 => true
이 확인 결과가 참이므로, 그래프에는 a에서 도달 가능한 음수 가중치 사이클이 존재한다는 것을 알 수 있다.
복잡도
이완 단계는 단순히 비교 작업을 수행하기 때문에 상수 시간(O(1))이 소요된다. 이 단계는 각 간선마다 한 번씩(Θ(|E|)) 수행되며, 간선은 |V|-1번 반복된다. 이는 전체 복잡도가 Θ(|V||E|)임을 의미하지만, 최적화를 통해 개선할 수 있다. 외부 루프가 실행되고 기록된 가중치에 변경 사항이 없으면 이완 단계를 안전하게 종료할 수 있다. 이 경우 Θ(|V|) 단계 대신 O(|V|) 단계로 실행될 수 있다(즉, 어떤 크기의 그래프에서도 최선의 경우는 상수 번의 반복이며, 최악의 경우 여전히 |V|-1번 반복된다).
음수 가중치 사이클을 확인하는 작업은 한 번 발견하면 즉시 반환하므로 O(|E|)이다. 출발 정점에서 도달 가능한 모든 음수 가중치 사이클을 찾으려면 Θ(|E|)번 반복해야 한다(현재는 사이클을 보고하지 않고, 단순히 사이클이 존재할 경우 nil을 반환한다).
따라서 벨만-포드 알고리즘의 총 실행 시간은 O(|V||E|)이다.
TODO
- 방향성 있고 가중치가 음수가 아닌 그래프에서 SSSP(단일 출발점 최단 경로)를 계산하기 위한 다익스트라 알고리즘
참고 자료
- Cormen, Leiserson, Rivest, Stein의 Introduction to Algorithms, Third Edition 24장 https://mitpress.mit.edu/books/introduction-algorithms
- 위키피디아: Bellman–Ford 알고리즘
Swift Algorithm Club을 위해 Andrew McKnight가 작성함