최단 거리 알고리즘에 대해 정리해 본다. <알고리즘 문제 해결 전략> 책을 참고했음을 밝힌다.
최단 거리 알고리즘은 말 그대로 시작 지점에서 도착 지점까지 이동하는 경로 중 가장 짧은 경로의 거리를 구하는 알고리즘이다. 장소와 길은 그래프로 나타내기 때문에, 그래프 이론과 밀접한 관련이 있다.
1. 다익스트라 알고리즘 (Dijkstra's algorithm)
가장 스탠다드한 최단 거리 알고리즘이다. 시작 정점을 지정하면 해당 정점에서 출발해서 다른 정점으로 도착할 때의 최단 거리를 알 수 있다. 길찾기 알고리즘을 적용하는 가장 흔한 예는 가중치(weight)가 있는 weighted graph이므로, 나중에 발견된 정점이 최단 거리일 수 있다. 즉, 단순한 BFS로는 최단 거리를 찾지 못하는 경우가 수없이 많다는 것이다.
다르게 말하면, 나중에 발견된 정점까지의 경로의 weight의 합(=거리)이 먼저 발견한 정점까지의 경로의 weight의 합보다 작다면, 나중에 발견한 정점에 대해 먼저 연산을 실행해야 한다는 것이다. 이러한 점 때문에 다익스트라 알고리즘에서는 BFS에서 큐를 사용하는 것과는 다르게 우선순위 큐(priority queue)를 사용한다. 우선순위 큐를 사용하면 나중에 발견된 정점이어도 값에 따라 먼저 연산할 수 있기에 다익스트라 알고리즘을 구현하는 데에 적합하다.
실제 구현
vector<vector<pair<int, int>>> adj; // 인접 그래프
int V; // 정점의 개수
vector<int> dijkstra(int start) {
vector<int> dist(V, numeric_limits<int>::max());
dist[start] = 0;
priority_queue<pair<int, int>> pq;
pq.push(make_pair(0, start));
while (!pq.empty()) {
int cost = -pq.top().first, here = pq.top().second; // *1
pq.pop();
if (dist[here] < cost) { continue; } // *2
for (int i = 0; i < adj[here].size(); ++i) {
int next = adj[here][i].first, nextCost = cost + adj[here][i].second;
if (dist[next] > nextCost) {
pq.push(make_pair(-nextCost, next)); // *1
dist[next] = nextCost;
}
}
}
return dist;
}
*1) 우선순위 큐는 기본적으로 가장 큰 값이 top에 오기 때문에, 가장 작은 값을 먼저 뽑기 위해서 부호를 바꾸어 저장해 준 후에 pop을 하는 과정에서 다시 부호를 바꾸어서 읽는다. (물론 greater<>를 넣어도 된다.)
*2) 이전 탐색에서 start부터 here까지의 경로가 더 짧은 것을 발견했으면 굳이 더 경로가 긴 곳에서 똑같은 계산을 할 필요가 없기 때문에 넘어간다. 참고로, dist[here] == cost인 경우는 이전에 기록한 최단 거리를 그대로 보고 있는 경우이기 때문에 당연히 계산해 주어야 한다.
2. 벨만-포드 알고리즘 (Bellman-Ford algorithm)
다익스트라 알고리즘은 음수 사이클이 있을 때 제대로 동작하지 않는다는 단점이 있다. 음수 사이클이 있다면 무한대로 반복했을 때 경로의 길이는 점점 짧아지기 때문에, 다익스트라 알고리즘에서는 무한 루프에 빠지게 된다. 또한, 그 구현에 따라서는 음수 사이클이 없더라도 음수 간선만 있는 경우에도 제대로 된 동작을 보장할 수 없는 경우가 있다. 벨만-포드 알고리즘은, 음수 간선이 있는 경우에도 제대로 된 동작을 보장할 수 있는 알고리즘이며, 음수 사이클이 있을 때에도 음수 사이클의 여부를 판단할 수 있다.
우리가 최단 거리를 찾기 위해 선택한 시작 정점을 s라고 하고, 임의의 두 정점을 u와 v라고 하자. 또, u와 v를 연결하는 간선의 weight가 w(u, v)라고 하자. 여기서, s에서 u까지의 최단 거리를 dist[u], s에서 v까지의 최단 거리를 dist[v]라고 했을 때, dist[v]는 dist[u]와 w(u, v)의 합보다 항상 같거나 작다. 이를 식으로 표현하면 아래와 같다.
dist[v] <= dist[u] + w(u, v)
벨만-포드 알고리즘은 위의 사실에 기반한 아이디어로 이루어져 있다.
먼저, 시작점에서 다른 정점까지의 거리를 저장하는 배열 upper[]를 생각해 보자. 처음에는 아무 것도 계산되지 않았으므로, 시작점을 제외한 upper의 모든 원소에는 아주 큰 값이 저장되어 있다. (일반적으로, 문제에서 계산했을 때 나올 수 있는 가장 긴 최단 거리보다도 큰 값이면 충분하다.) 그리고 upper[s]=0으로 초기화되어 있다. 이때, 위의 사실에 입각하여 upper[u] + w(u, v) < upper[v]일 때를 생각해 보자. 우리는 이 알고리즘이 최단 거리를 계산해 준다는 것을 알고 있기 때문에 upper[v]의 값은 항상 최단 거리를 계산하는 dist[v]보다 크거나 같다는 사실을 알 수 있다. 그러므로, upper[v]를 upper[u] + w(u, v)로 줄일 수 있다. 이 과정을 완화(relax)라고 한다.
이러한 완화 과정을 모든 간선에 대해 실행하고, 완화할 때마다 upper는 최단 거리에 가까워지게 된다.
종료 조건에 대해 생각해 보기
시작 정점 s에서 도착 정점 d 사이의 최단 경로가 {s, a, b, c, d}라고 생각해 보자. 이 알고리즘은 언제 최단 거리를 찾게 될까? 벨만-포드 알고리즘에서 upper가 초기화되었을 때는 upper[s]만이 최단 거리가 보장된다. 이후 모든 간선에 한번씩 완화를 시도한다면, s에서 a로 가는 완화도 이루어지게 된다. 이때, 완화된 결과인 upper[a]가 최단 거리가 아니라면 s부터 d까지의 최단 경로도 {s, a, b, c, d}가 될 수 없으므로, 모든 간선에 대해 한번씩 완화를 시도했을 때 upper[a]는 최단 거리가 됨을 알 수 있다.
이후 모든 간선에 대해 한번씩 완화를 시도하는 과정을 반복하면 다음은 upper[b]가 최단 거리임이 보장되고, 다음은 upper[c]가 최단 거리임이 보장된다. 즉, 완화 시도를 한 번 반복할 때마다 최단 거리가 보장되는 정점이 하나 이상 늘어나게 되는 것이다. 그래프에서 정점의 수를 V라고 한다면, 아무리 긴 최단 경로여도 간선은 V-1개밖에 없고, 즉 V-1번 완화를 시도하면 모든 정점에 대해 최단 거리를 찾을 수 있다는 말이 된다.
음수 사이클의 판정
음수 사이클이 존재한다는 것은 V-1번 완화를 시도한 후에도 다음 완화에서 또 완화가 성공하게 됨을 말한다. 즉, V-1번 완화를 시도한 후에 한 번 더 완화를 시도해서 성공한다면 음수 사이클이 있다고 판정하면 된다.
실제 구현
vector<vector<pair<int, int>>> adj; // 인접 그래프
int V; // 정점의 개수
vector<int> bellmanFord(int start) {
vector<int> upper(V, numeric_limits<int>::max());
upper[start] = 0; // 시작 정점은 0으로 초기화
bool updated;
for (int iter = 0; iter < V; ++iter) { // V번 완화를 시도한다
updated = false; // 이번 반복에서 완화가 성공했는가?
for (int here = 0; here < V; ++here) {
for (int i = 0; i < adj[here].size(); ++i) {
int next = adj[here][i].first, cost = adj[here][i].second;
if (upper[here] != numeric_limits<int>::max() && // *1
upper[next] > upper[here] + cost) {
upper[next] = upper[here] + cost;
updated = true;
}
}
}
if (!updated) { break; }
}
if (updated) { upper.clear(); } // *2
return upper;
}
*1) upper[here]가 INF이면 아직 이 값도 한번도 완화되지 못했기 때문에 해당 간선을 완화하려고 하는 것은 의미가 없다. <알고리즘 문제 해결 전략>에서는 해당 비교문 없이 두 번째 비교문만으로 완화를 시도하는데, 이 경우 큰 값으로 초기화했을 때 오버플로가 일어날 가능성이 있기 때문에 해당 비교문을 추가하였다. 또, 음수 간선이 있을 수 있기 때문에 start에서 u로 가는 경로가 있는지의 여부도 upper[u] == INF가 아닌, upper[u] == INF - (적당히 큰 값)으로 해줘야 하기 때문에 값 계산에서 실수가 일어날 가능성이 있다.
*2) 완화를 V번 시도했기 때문에, for문을 빠져나온 후에도 updated가 true라는 것은 V번째 완화도 성공했음을 의미한다. 즉 이것은 음수 사이클이 있음을 의미한다. 해당 코드에서는 음수 사이클이 있으면 빈 벡터를 리턴하도록 했는데, 문제에 따라서 이 부분은 입맛에 맞게 변형하면 된다.
3. 플로이드-워셜 알고리즘 (Floyd-Warshall algorithm)
위에서 나온 다익스트라 알고리즘이나 벨만-포드 알고리즘의 경우 시작점을 지정해줘야 한다는 특징이 있다. 모든 시작점에 대해서의 최단 거리를 알고 싶다면 이러한 알고리즘을 정점의 수만큼 반복해야 한다는 뜻이기도 하다. 플로이드-워셜 알고리즘은, 모든 정점 쌍에 대해서 최단 거리를 알고 싶을 때 이를 더 효율적으로 계산해 주는 알고리즘이다.
두 정점 u와 v를 잇는 경로는 u와 v 사이에 임의의 정점을 지날 수 있다. 이 임의의 정점들을 경유점이라 하자. 또, 임의의 정점 집합 S의 정점만 이용하여 u에서 v로 가는 최단 거리를 D_S(u, v)라고 하자. 이렇게 정의했을 때, 모든 정점의 집합을 V라고 하면 우리가 구하고자 하는 값은 D_V(u, v)이며, w(u, v)는 D_∅(u, v)이다.
이때, 특정 정점의 집합 S를 경유점으로 할 때 임의의 정점 x∈S에 대하여 최단 경로는 x를 경유하지 않을 수도, 경유할 수도 있다. 최단 경로가 x를 경유하지 않는다면, D_S(u, v)는 D_S-{x}(u, v)와 같고, 반대로 최단 경로가 x를 경유한다면 D_S(u, v)는 D_S(u, x)+D_S(x, v)와 같다.
동적 계획법과 최적화
여기서 S_k = {0, 1, 2, ..., k}라 하고, C_k = D_S_k라 하면,
C_k(u, v) = min(C_k-1(u, k) + C_k-1(k, v), C_k-1(u, v))임을 알 수 있다.
k를 거치는 경우와 k를 거치지 않는 경우 중 더 작은 값을 C_k(u, v)로 취하는 점화식을 만든 것이다. 이 점화식을 보면, C_k의 값은 C_k-1의 값에 종속되어 있기 때문에 동적 계획법을 통해 플로이드-워셜 알고리즘을 구현할 수 있겠다는 생각을 떠올리기는 어렵지 않을 것이다. 더 나아가, 우리는 k번째를 볼 때는 k-1만 고려하고, 그보다 작은 값은 고려하지 않기 때문에 동적 계획법에 사용할 배열의 크기는 2*V*V로 줄일 수 있음을 생각할 수 있다. ([k%2][u][v]로 접근할 수 있기 때문이다.)
그러나 여기서 C_k-1(u, k)에 대해 한번 더 생각해 보자. C_k(u, k)와 C_k-1(u, k)는 어떤 차이가 있는가? u에서 k로 가는 최단 경로에서 '경유점'으로 하여금 k를 경유할 수 있는가, 경유할 수 없는가의 차이 뿐이다. k는 경유점이 아니라 양 끝 정점에 속하기 때문에, C_k(u, k)와 C_k-1(u, k)는 차이가 없음을 알 수 있다. 즉, 동적 계획법 패러다임을 이용하지만 추가적인 배열이 아예 필요하지 않다는 결론에 도달하게 된다.
실제 구현
int adj[V][V]; // 인접 행렬 *1
void floydWarshall() {
for (int i = 0; i < V; ++i) {
adj[i][i] = 0;
}
for (int k = 0; k = V; ++k) {
for (int i = 0; i < V; ++i) {
for (int j = 0; j < V; ++j) {
adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
}
}
}
}
*1) 모든 정점의 쌍에 대해 최단 거리를 구하기 때문에 먼저 설명한 두 알고리즘에서 채용하는 인접 그래프와 달리 플로이드-워셜 알고리즘에서는 인접 행렬이 적절하다. 또한, 두 정점을 잇는 간선이 없는 경우 아주 큰 값을 넣는다. adj[i][k] + adj[k][j]와 같은 연산에서 오버플로우가 일어날 수 있기 때문에 INF는 적절하지 않고, 987654321과 같은 값이 적절하다.
(987654321은 int형에서 충분히 큰 값인데다가 입력하기도 쉽고, 오타가 나더라도 발견하기 쉬우며, 두 번 더했을 때 INT_MAX에 가까운 값이 나오면서도 오버플로우가 일어나지 않는다.)
평범한 최단 거리 문제인가?
다익스트라 알고리즘의 사용을 고려해 본다.
음수 간선/사이클의 가능성이 있는가?
벨만-포드 알고리즘의 사용을 고려해 본다.
모든 정점 쌍에 대하여 최단 거리를 구해야 하는가?
플로이드-워셜 알고리즘의 사용을 고려해 본다.
최단 경로 알고리즘은 '거리'라는 단어에 휘둘리지 않는다면 거리가 아닌 시간 등 weight(cost)로 표현될 수 있는 대부분의 경우에서 사용할 수 있으므로 꼭 숙지하는 것이 중요하다.
또한, 정말 경로라는 단어가 필요하지 않은 경우 최단 '거리'라고 표현했는데, 값을 갱신할 때 here를 기록해놓는 등의 방법을 이용하면 최단 거리일 때의 경로 또한 역추적이 가능할 수 있다.
'공부 > PS' 카테고리의 다른 글
[BOJ 1949] 우수 마을 (Gold II) (0) | 2022.11.17 |
---|---|
백준 64일 스트릭 회고 (0) | 2022.11.03 |
PS에 편한 C++ 문법 (1) | 2022.09.29 |
KMP 알고리즘 (0) | 2022.02.13 |