최단 경로 알고리즘은 말 그대로, 출발지와 도착지 사이의 가장 짧은 경로를 찾는 알고리즘입니다. 다른 말로는 '길 찾기' 문제라고도 합니다.
보통 이런 문제들은 그래프 자료구조를 이용해 표현되는데, 출발지와 도착지, 그리고 그 외 중간 지점은 노드, 각 지점 사이의 경로와 거리는 엣지로 표현됩니다. 문제의 유형도 다양한데, '특정 지점 A에서 특정 지점 B까지의 최단 경로를 구하기', '모든 지점에서 다른 모든 지점까지의 최단 경로를 구하기' 등이 있으며, 이에 맞는 알고리즘을 알고 있다면 문제를 조금 더 수월하게 풀 수 있습니다.
실제 코딩 테스트에서는 최단 경로를 모두 출력하기보다는, 최단 거리만을 출력하는 문제가 많이 출제된다고 합니다.
대표적인 알고리즘은 다음과 같습니다:
- 다익스트라 (Dijkstra) 최단 경로 알고리즘
- 플로이드-워셜 (Floyd-Warshall) 알고리즘
- 벨만-포드 (Bellman-Ford) 알고리즘
이 중 다익스트라, 플로이드-워셜 알고리즘 두 종류를 다루고자 합니다. 앞서 공부한 그리디 알고리즘과 다이나믹 프로그래밍이 최단 경로 알고리즘에서 중요한 부분으로 등장합니다.
다익스트라 최단 경로 알고리즘
다익스트라 (Dijkstra) 최단 경로 알고리즘은, 특정 지점 A에서 다른 노드로 갈 때, 각각의 최단 경로를 구해 주는 알고리즘입니다. 이 알고리즘은 간선이 음의 값을 가지지 않을 때 정상적으로 동작하는데, 현실 세계에서 도시와 도시 사이의 거리가 음수가 될 수는 없으므로, 실제로 우리가 사용하는 GPS는 다익스트라 알고리즘을 자주 채택합니다.
다익스트라 알고리즘은 그리디 알고리즘의 한 종류입니다. 매번 '가장 비용이 적은 노드' 를 선택하기 때문입니다. 알고리즘의 구조를 살펴봅시다.
- 출발 노드를 설정합니다.
- 최단 거리 테이블을 초기화 합니다.
- 방문하지 않은 노드들 중에서 최단 거리가 가장 짧은 노드를 선택합니다.
- 해당 노드를 거쳐, 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신합니다.
- 3, 4번 과정을 반복하면, 결과적으로 원하는 값을 얻을 수 있습니다.
다익스트라 알고리즘은 최단 경로를 구하는 과정에서 '각 노드에 대한 현재까지의 최단 거리' 정보를 늘 배열에 저장하고, 이를 매번 갱신합니다. 즉 A -> B 경로가 거리가 13이었는데, 새로 구한 과정에서 8이라는 거리를 얻는다면, 이제부터는 8이 최단 경로라고 판단하고 기록하는 것입니다. '방문하지 않은 노드 중에서 현재 최단거리가 가장 짧은 노드' 를 확인하고, 그 노드에 대해 4번 과정을 수행하므로, 그리디 알고리즘이라고 볼 수 있습니다.
다익스트라 알고리즘을 먼저 그림과 같이 소개한 후, 알고리즘을 구현하는 두 가지 방법에 대해 다루도록 하겠습니다.
다음과 같은 그래프가 있을 때, 1번 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 문제를 생각해 봅시다. 각 경로에는 방향성이 존재합니다.
단계 0. 1번 노드에서 출발합니다. 우선, 다른 모든 노드로의 거리를 무한대로 초기화 합니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 무한 | 무한 | 무한 | 무한 | 무한 |
여기서 무한이라 함은, 충분히 큰 수를 나타냅니다. 999,999,999와 같은 수를 사용하거나, 1e9 (10억) 등으로 나타냅니다. 또는, 거리의 최댓값이 이미 주어져 있다면 (예: 100), 최댓값보다 조금 더 큰 수로 초기화해도 좋습니다 (101 등).
단계 1. 1번 노드를 거쳐, 다른 노드로 가는 비용을 계산합니다. 1번 노드에서 갈 수 있는 노드는 2, 3, 4번 노드이며, 비용은 2번 노드가 2 (0+2), 3번 노드가 5 (0+5), 4번 노드가 1 (0+1) 입니다. 현재 이미 배열에 저장되어 있는 거리와 비교했을 때, 각 값들은 무한보다 작으므로, 새로운 값으로 갱신합니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 5 | 1 | 무한 | 무한 |
이미 처리한 노드 (방문한 노드)는 글자색을 검정색으로 하였습니다.
단계 2. 이후의 모든 단계에서도 앞과 비슷한 과정을 반복합니다. 즉, 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택해야 합니다.
이번에는 1번 노드에서 가장 가까운 4번 노드에서 시작하게 됩니다. 4번 노드에서 갈 수 있는 노드는 3번, 5번 노드입니다. 여기서, 우리가 이미 구해둔 출발점에서 4번 노드까지 가는 거리는 1이므로, 이를 합산하도록 합니다.
비용은 3번 노드가 4 (1+3), 5번 노드가 2 (1+1) 입니다. 이 두 값 모두 기존의 배열에 담겨 있던 값 (5, 무한) 보다 작으므로, 값을 갱신합니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 4 | 1 | 2 | 무한 |
단계 3. 다음으로 방문하지 않은 노드들 중에서, 출발점인 1번 노드에 가장 가까운 노드는 2번 노드입니다. 5번 역시 거리가 같은데, 이럴 때는 일반적으로 노드 번호가 더 낮은 쪽을 고릅니다.
2번 노드에서 갈 수 있는 노드는 3번, 4번 노드입니다. 비용은 3번 노드가 5 (2+3), 4번 노드가 4 (2+2) 이며, 둘 다 기존의 값 (4, 1) 보다 큽니다. 따라서 배열의 값을 갱신하지 않고 넘어갑니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 4 | 1 | 2 | 무한 |
단계 4. 다음 순서는 5번 노드입니다. 5번 노드에서 갈 수 있는 노드는 3번, 6번 노드입니다.
출발점 (1번 노드) 에서 5번 노드까지 가는 현재까지의 최단 거리는 2입니다. 5번 노드에서 3번 노드까지의 비용은 1, 6번 노드까지의 비용은 2이므로, 총 비용은 3 (2+1), 4 (2+2) 가 됩니다. 기존에 배열에 저장된 값인 무한보다 작으므로, 배열의 값을 갱신해 줍니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 3 | 1 | 2 | 4 |
단계 5. 방문하지 않은 노드는 3번, 6번 노드이며, 둘 다 출발점으로부터의 거리는 4입니다. 3번 노드를 선택합니다.
3번 노드에서 갈 수 있는 노드는 2번, 6번 노드입니다. 거리는 각각 7 (4 + 3), 9 (4 + 5) 가 되는데, 모두 기존의 값보다 큽니다. 따라서 배열의 값을 갱신하지 않고 넘어갑니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 3 | 1 | 2 | 4 |
단계 6. 마지막으로 남은 6번 노드를 확인해 줍니다. 출발점으로부터 6번 노드까지의 거리는 4이며, 6번 노드에서 갈 수 있는 노드는 없습니다. 따라서 경로 탐색을 종료합니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 3 | 1 | 2 | 4 |
탐색을 종료한 결과는 위와 같습니다. 1번 노드부터 출발했을 때, 2, 3, 4, 5, 6번 노드까지의 최단 거리는 각각 2, 4, 1, 2, 4임을 의미합니다.
다익스트라 알고리즘은 '방문하지 않은 노드' 중에서 가장 최단 거리가 짧은 노드를 선택하는 과정을 반복합니다. 이렇게 선택된 노드는 '최단 거리' 가 완전히 선택된 노드이므로, 더 이상 거리 갱신이 발생하지 않습니다. 즉, 기준대로의 순서에 맞추어, 한 노드씩 최단 거리를 확실히 찾아 가는 과정이라고 이해할 수 있습니다.
따라서 마지막 (6번) 노드에 대해서는 다른 노드를 거쳐 가는 경우를 확인할 필요가 없습니다. 이미 나머지 노드, 위 예시에서는 나머지 5개 노드에 대한 최단 거리가 확정된 상태이므로, 더 이상 테이블이 갱신될 수 없기 때문입니다.
구현
앞서 언급한 대로, 다익스트라 알고리즘은 두 가지 방법으로 구현할 수 있습니다. 첫 번째로, 간단히 구현하는 방법을 소개합니다. 다익스트라에 의하여 처음 고안되었던 방법으로, O(V^2)의 시간 복잡도를 가지며, V는 노드의 개수를 의미합니다.
이 알고리즘은 직관적이고 쉽게 이해할 수 있지만, 후술할 두 번째 방법에 비해 시간복잡도가 더 높습니다.
처음에 각 노드에 대한 최단 거리를 담는 1차원 배열을 생성하고, 매 단계마다 '방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택' 하기 위해 매 단계마다 배열의 모든 원소를 확인 (순차 탐색) 합니다.
void dijkstra(int start) {
d[start] = 0;
visited[start] = true;
for (int i = 0; i < graph[start].size(); i++)
d[graph[start][i].first] = graph[start][i].second;
for (int i = 0; i < n-1; i++) {
int now = getSmallestNode();
visited[now] = true;
for (int j = 0; j < graph[now].size(); j++) {
int cost = d[now] + graph[now][j].second;
if (cost < d[graph[now][j].first])
d[graph[now][j].first] = cost;
}
}
}
함수를 포함한 전체 코드 보기:
getSmallestNode는 현재까지 방문하지 않은 노드들 중, 출발점으로부터 최단 거리를 가지는 노드를 반환하는 함수입니다.
최단 거리가 가장 짧은 노드를 매번 선형 탐색하므로 O(V)의 시간이 걸리고, 현재 노드와 연결된 노드를 매번 확인하므로 다시 한 번 O(V)의 시간이 걸리게 되어, 총 O(V^2)의 시간 복잡도를 가지게 됩니다.
따라서 코딩 테스트에서, 노드의 개수가 10,000개를 넘어가는 문제라면, 이 방법으로는 시간 초과에 걸리게 됩니다.
다음으로, 개선된 다익스트라 알고리즘을 소개합니다. 이 방법은 최악의 경우에도 O(E log V) 를 가지게 됩니다. 앞선 경우와 마찬가지로, V는 노드의 개수이며, E는 간선의 개수입니다.
앞선 간단한 다익스트라 알고리즘의 경우, 매번 최단 거리가 가장 짧은 노드를 찾기 위해 선형 탐색을 진행했습니다. 하지만 선형 탐색이 아닌, 더 빠른 탐색 방법을 이용한다면 어떨까요?
이를 위해, 개선된 다익스트라 알고리즘에서는 힙 (heap) 자료구조를 이용합니다. 특정 노드까지의 최단 거리에 대한 정보를 힙에 담아 처리하여, 출발점으로부터 가장 거리가 짧은 노드를 더 빠르게 찾을 수 있습니다. 대략 O(log V)의 시간이 걸리게 됩니다. V = 1,000,000일 때, 간단한 다익스트라 알고리즘은 탐색에 약 1,000,000번의 연산이 필요하다면, 개선된 다익스트라 알고리즘은 약 20번의 연산이 필요하게 되는 것입니다.
힙에 대한 더 자세한 내용은 이 글 (외부 블로그) 에 잘 설명되어 있으니 참고하시기 바랍니다.
최소 힙을 이용하면 '가장 값이 작은 원소' 가 추출되는 특징이 있으며, 이를 다익스트라 알고리즘의 '가장 가까운 원소 찾기' 에 적용해 봅니다. 단계별로 우선순위 큐의 변화에 주목하며 알고리즘의 동작 과정을 살펴보겠습니다. 가장 가까운 노드 외의 다른 부분은 아까와 유사합니다.
마찬가지로 1번 노드가 출발점입니다. 그 외 다른 노드들의 거리는 무한으로 초기화 합니다.
단계 0. 우선순위 큐에 1번 노드를 넣습니다. 1번 노드에서 1번 노드까지의 거리는, 스스로 도달하는 거리이므로 0이 됩니다. 우선순위 큐는 거리를 기준으로 합니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 무한 | 무한 | 무한 | 무한 | 무한 |
| 우선순위 큐 | (거리 0, 노드 1) | |||||
단계 1. 우선순위 큐를 이용하고 있으므로, 거리가 가장 짧은 노드를 선택하기 위해서는, 우선순위 큐에서 노드를 꺼내기만 하면 됩니다. 거리가 짧은 노드가 우선순위 큐의 최상위 원소로 이미 위치해 있기 때문입니다.
꺼내고 나면 큐가 비어 있을 것입니다. 이후에 인접한 노드들 중 방문한 노드가 있다면 큐에 새로운 노드들을 집어 넣고, 방문한 노드가 없다면 그대로 탐색이 종료됩니다.
우선순위 큐에서 노드를 꺼낸 후, 해당 노드를 이미 처리한 적이 있다면 무시하고, 그렇지 않다면 처리하면 됩니다.
위 단계에서 노드를 꺼내면 (0, 1)이 나옵니다. 1번 노드에서 1번 노드로 가는 거리가가 0이라는 뜻입니다. 이어서, 1번 노드에 인접한 2, 3, 4번 노드로 가는 최소 비용을 계산합니다. 앞에서 했듯 각각 2, 5, 1이며, 최단거리 배열을 갱신하고, 우선순위 큐에 (2, 2), (5, 3), (1, 4)를 집어넣습니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 5 | 1 | 무한 | 무한 |
| 우선순위 큐 | (거리 1, 노드 4), (거리 2, 노드 2), (거리 5, 노드 3) | |||||
단계 2. 우선순위 큐에서 원소를 하나 꺼냅니다. 이 노드는 아직 방문하지 않은 상태여야 합니다. 거리 1을 가지는, 노드 4가 되겠지요.
노드 4를 기준으로, 노드 4에서 갈 수 있는 노드들을 확인합니다. 3번, 5번 노드로 갈 수 있고, 비용은 각각 4, 2입니다. 기존의 최단거리 배열에 기록된 정보보다 값이 작기 때문에 값의 갱신이 발생하고, 우선순위 큐에는 (4, 3), (2, 5) 를 집어넣게 됩니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 4 | 1 | 2 | 무한 |
| 우선순위 큐 | (거리 2, 노드 2), (거리 2, 노드 5), (거리 4, 노드 3), (거리 5, 노드 3) | |||||
단계 3. 우선순위 큐에서 원소를 하나 꺼냅니다. 이 노드는 아직 방문하지 않은 상태여야 합니다. 거리 2를 가지는, 노드 2가 되겠지요.
2에서 갈 수 있는 노드는 3, 4번 노드이고, 거리는 각각 5, 4입니다. 두 값 모두 최단거리 배열에 기록된 정보보다 값이 크기 때문에 갱신은 발생하지 않고, 우선순위 큐에도 아무것도 넣지 않게 됩니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 4 | 1 | 2 | 무한 |
| 우선순위 큐 | (거리 2, 노드 5), (거리 4, 노드 3), (거리 5, 노드 3) | |||||
단계 4. 우선순위 큐에서 원소를 하나 꺼냅니다. 이 노드는 아직 방문하지 않은 상태여야 합니다. 거리 2를 가지는, 노드 5가 되겠지요.
5에서 갈 수 있는 노드는 3, 6번 노드이고, 거리는 3, 4입니다. 최단거리 배열에 기록된 정보보다 값이 작기 때문에, 3까지의 거리는 4에서 3으로, 6까지의 거리는 무한에서 4로 갱신되며, 우선순위 큐에는 (3, 3), (4, 6) 을 집어넣게 됩니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 3 | 1 | 2 | 4 |
| 우선순위 큐 | (거리 3, 노드 3), (거리 4, 노드 3), (거리 4, 노드 6), (거리 5, 노드 3) | |||||
단계 5. 마찬가지로 원소 (3, 3)을 꺼냅니다. 최단거리 테이블이 갱신되지 않고, 우선순위 큐에도 아무것도 삽입되지 않습니다. 따라서 결과는 다음과 같습니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 3 | 1 | 2 | 4 |
| 우선순위 큐 | (거리 4, 노드 3), (거리 4, 노드 6), (거리 5, 노드 3) | |||||
단계 6. 원소 (4, 3)을 꺼냅니다. 노드 3번은 이미 방문했던 노드이므로, 무시하고 노드를 버립니다. 이후 우선순위 큐의 상태는 다음과 같습니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 3 | 1 | 2 | 4 |
| 우선순위 큐 | (거리 4, 노드 6), (거리 5, 노드 3) | |||||
단계 7. 원소 (4, 6)을 꺼냅니다. 6번 노드에서 갈 수 있는 곳은 아무 노드도 없습니다. 따라서, 방문 처리만 하고 넘어갑니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 3 | 1 | 2 | 4 |
| 우선순위 큐 | (거리 5, 노드 3) | |||||
단계 8. 마지막으로 남은 원소 (5, 3)을 꺼냅니다. 노드 3번은 이미 방문했던 노드이므로, 무시하고 노드를 버립니다. 이후 우선순위 큐의 상태는 다음과 같습니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 3 | 1 | 2 | 4 |
| 우선순위 큐 | ||||||
우선순위 큐가 비었으므로, 탐색을 종료합니다.
탐색을 마친 후 출발점 (노드 1번)으로부터 각 노드까지의 최단 거리는 0, 2, 3, 1, 2, 4라는 결과를 얻었습니다. 이는 앞서 간단한 버전과 같은 결과이지만, 훨씬 빠르게 동작합니다. getSmallestCode()라는 함수를 추가적으로 작성할 필요가 없는데, 앞서 설명하였듯 우선순위 큐를 이용하여 탐색 과정을 획기적으로 단축했기 때문입니다.
void dijkstra(int start) {
priority_queue<pair <int, int> > pq;
pq.push(make_pair(0, start));
d[start] = 0;
while (!pq.empty()) {
int distance = -pq.top().first; //현재 노드까지의 비용
int now = pq.top().second; //현재 노드
pq.pop();
if (distance > d[now]) continue;
for (int i = 0; i < graph[now].size(); i++) {
int cost = distance + graph[now][i].second;
if (cost < d[graph[now][i].first]) {
d[graph[now][i].first] = cost;
pq.push(make_pair(-cost, graph[now][i].first));
}
}
}
}
전체 코드 보기:
개선된 다익스트라 알고리즘의 시간 복잡도는, 언급한 대로 O(E log V)입니다. 훨씬 빠르게 동작하는 편입니다.
코드에서 확인할 수 있듯, 한 번 처리된 노드는 더 이상 처리되지 않습니다. 즉, 노드를 하나씩 꺼내 검사하는 while 문은 V 이상으로는 반복되지 않습니다. 또, 각각 반복될 때마다 연결된 간선들 (E)를 모두 확인합니다.
시간복잡도에 대해서 조금 더 자세히 다루어 보겠습니다. 전체 다익스트라 최단 경로 알고리즘은 E개의 원소를 우선순위 큐에 모두 넣었다가 모두 빼내는 연산과 유사합니다. N개의 원소를 가지고 힙 자료구조에 전부 넣었다가 빼는 과정은 O(N log N)의 시간복잡도를 가집니다. 마찬가지로 O(E log E)의 시간복잡도를 가진다고 할 수 있습니다.
이때 중복 간선을 포함하지 않는 경우, E < V^2가 항상 성립합니다. 모든 노드끼리 전부 연결되어 있다고 가정하면, 간선의 개수는 약 V^2개가 되므로, E는 항상 V^2보다 작을 수밖에 없는 것입니다. 즉, log E는 log V^2보다 작습니다. log V^2는 로그함수이므로, 2 log V 의 형태로 나타낼 수 있고, 시간복잡도를 나타낼 때 곱해진 상수는 무시할 수 있습니다. 즉, O(2 log V) = O(log v)가 성립합니다. 따라서, 다익스트라 알고리즘의 전체 시간 복잡도는 O(E log E) < O(E log V)이므로, O(E log V) 라고 나타낼 수 있습니다.
다익스트라 알고리즘은 코딩 테스트에서 매우 중요합니다. 위 두 코드를 모두 백지 상태에서 적어낼 수 있어야 합니다. 또, 우선순위 큐를 이용하는 다른 문제 유형과도 흡사하다는 특징이 있는데, 그 예로 최소 신장 트리 문제를 풀 때도 일부 알고리즘 (Prim 알고리즘 등)의 구현이 다익스트라 알고리즘과 흡사한 부분이 있습니다. 따라서 다익스트라 알고리즘을 잘 익혀 두시길 바랍니다.
플로이드 워셜 알고리즘
플로이드-워셜 (Floyd-Warshall) 알고리즘은 다익스트라 알고리즘과 유사하게, 최단 경로를 구할 때 쓰는 알고리즘입니다. 다른 점이라면, 한 출발점을 정하고 그곳으로부터 다른 특정 지점까지의 최단 경로를 구하는 경우 사용하지만, 플로이드-워셜 알고리즘은 '모든 지점에서 다른 모든 지점까지' 최단 경로를 구하는 경우 사용합니다.
플로이드-워셜 알고리즘의 동작 과정은 다음과 같습니다. 단계마다 최단 거리를 가지는 노드를 하나씩 반복적으로 선택합니다. 해당 노드를 거쳐가는 경로를 확인하며, 최단 거리 테이블을 갱신하는 방식으로 동작합니다. 차이점이라면, 매번 '방문하지 않은 노드 중에서 최단 거리를 를 갖는 노드' 를 찾을 필요가 없습니다. 노드의 개수가 N개일 때, N번의 단계를 수행하며, 각 단계마다 O(N^2)의 연산을 통해, 현재 노드를 거쳐 가는 모든 노드를 확인합니다. 따라서 알고리즘의 전체 시간 복잡도는 O(N^3)이 됩니다.
모든 노드에 대하여 다른 모든 노드로 가는 경로에 대한 정보를, 2차원 배열 형태에 저장하게 됩니다. 또, 플로이드-워셜 알고리즘은 다이나믹 프로그래밍에 속하기도 합니다. '점화식에 맞게' 2차원 리스트를 갱신합니다.
알고리즘을 조금 더 자세히 알아보겠습니다. 각 단계에서는 해당 노드를 거쳐 가는 경우를 고려합니다. 예를 들어, A -> B -> C 노드로 가는 경로가 있다고 합시다. 이번 단계에 B번 노드를 중심으로 살펴본다면, A -> B -> C 의 비용을 확인한 후에 최단 거리를 갱신하는 것입니다. 이를테면 원래 A -> C는 3이었는데, A -> B -> C가 비용이 2임이 드러난다면, A -> B의 비용을 2로 갱신하는 것입니다.
따라서 알고리즘에서는 현재 확인하고 있는 노드를 제와한, N-1개의 노드 중에서 서로 다른 노드 (A, B)를 선택하게 됩니다. 이후 A -> 현재 노드 -> B의 비용을 확인한 후 최단 거리 정보를 갱신하는 것입니다. (N-1)P2 (P는 permuation을 의미합니다.) 개의 쌍을 단계마다 반복하여 확인하게 됩니다. 이때 N-1개의 원소 중 2개를 중복되지 않게 선택하는 과정은 N^2라고 볼 수 있기 때문에, 이 과정의 시간 복잡도는 O(N^2)가 되며, 따라서 전체 시간복잡도는 O(N^3)이 됩니다.
구체적인 점화식은 다음과 같습니다:
d[a][b] = min(d[a][b], d[a][k] + d[k][b])
직접 예를 들어 보도록 하겠습니다.
위와 같은 그래프가 있을 떄, 초기 테이블을 먼저 설정합니다. 간선이 연결 된 경우 간선의 값을 넣고, 연결되지 않은 경우 무한을 값으로 넣습니다.
| 출발/도착 | 1 | 2 | 3 | 4 |
| 1 | 0 | 4 | INF | 6 |
| 2 | 3 | 0 | 7 | INF |
| 3 | 5 | INF | 0 | 4 |
| 4 | INF | INF | 2 | 0 |
그 다음, 1번 노드를 거쳐 가는 경우를 모두 고려합니다. 이때는 3P2 = 6가지 경우에 따라 고민하게 됩니다. 앞의 점화식의 형태에 맞추어 고려해보도록 합니다:
d[2][3] = min(d[2][3], d[2][1] + d[1][3])
d[2][4] = min(d[2][4], d[2][1] + d[1][4])
d[3][2] = min(d[3][2], d[3][1] + d[1][1])
d[3][4] = min(d[3][4], d[3][1] + d[1][4])
d[4][2] = min(d[4][2], d[4][1] + d[1][2])
d[4][3] = min(d[4][3], d[4][1] + d[1][3])
기존의 값과 비교하여, 1번 노드를 거쳐 가는 값이 더 적은 경우, 그 값으로 교체해 준다는 의미입니다. 거쳐가는 경로가 없을 경우, INF가 더해져 값이 교체되지 않을 것이고, 거쳐가는 경우가 값이 더 큰 경우 역시 값이 교체되지 않을 것입니다.
위 과정을 거치면 표가 다음과 같이 바뀝니다:
| 출발/도착 | 1 | 2 | 3 | 4 |
| 1 | 0 | 4 | INF | 6 |
| 2 | 3 | 0 | 7 | 9 |
| 3 | 5 | 9 | 0 | 4 |
| 4 | INF | INF | 2 | 0 |
위 과정을 2, 3, 4번 노드를 거쳐가도록 반복해 주면 됩니다. 결과는 아래와 같습니다:
| 출발/도착 | 1 | 2 | 3 | 4 |
| 1 | 0 | 4 | 8 | 6 |
| 2 | 3 | 0 | 7 | 9 |
| 3 | 5 | 9 | 0 | 4 |
| 4 | 7 | 11 | 2 | 0 |
위 표는 모든 노드로부터 다른 모든 노드까지의 최단 거리 정보를 담고 있습니다. 예를 들어, d[1][3] = 8인데, 이는 1번 노드에서 출발하여 3번 노드까지 가는 최단 거리가 8임을 의미합니다.
이것을 코드로 옮겨 보겠습니다.
내용이 매우 단순하여 코드로 옮기기에 큰 어려움이 없습니다.
이렇게 최단 경로를 찾는 두 알고리즘, 다익스트라 알고리즘과 플로이드-워셜 알고리즘을 알아보았습니다.
경로 찾기 문제는 코딩 테스트에 빈번하게 나오는 내용이니만큼, 알고리즘을 잘 이해하고 구현할 수 있는 것이 중요합니다.
*본 글은 "나동빈, 이것이 취업을 위한 코딩 테스트다 with 파이썬 (한빛미디어, 2020)" 를 참고하여 작성하였습니다.
'알고리즘, 문제해결 > 알고리즘, 자료구조' 카테고리의 다른 글
| [SQL] SELECT (0) | 2021.03.10 |
|---|---|
| 그래프 이론 (0) | 2021.02.12 |
| 다이나믹 프로그래밍 (0) | 2021.02.05 |
| 이진 탐색 (0) | 2021.02.04 |
| 정렬 (0) | 2021.02.04 |
댓글