최단 거리 알고리즘
그래프에서 간선들 사이의 가중치와 방향이 있을 때, 한 정점에서 다른 정점들까지의 최단 거리를 구할 수 있는 알고리즘은 다익스트라, 벨만포드, A* 등이 있고, 모든 정점에서 모든 정점의 최단 거리를 구하는 알고리즘에는 플로이드 워셜 알고리즘이 있다.
해당 알고리즘들을 응용하여 최단 거리를 가지는 경로를 구하는 방법도 있지만, 이 글에서는 다익스트라 알고리즘을 활용하여 최단 거리만 구해보겠다.
먼저 우선순위 큐를 사용하지 않는 최초의 다익스트라 알고리즘은 아래 과정과 같고 O(V2) 의 시간 복잡도를 갖는다. (2중 for 문 구조)
- 시작 노드 결정
- 현재 노드를 기준으로 각 노드의 최소 비용을 계산
- 방문 하지 않은 노드 중 최소 비용의 노드를 선택
- 선택된 노드를 기준으로 거리 비용을 계산하여 더 가까울 경우 갱신
- 3~4를 반복하여 모든 노드를 방문
여기서 힙(우선순위 큐) 구조를 사용하면 O(log N)의 시간 복잡도로 값을 구할 수 있는데, 모든 간선에 대해 비교를 해야하므로 우선순위 큐로 구현된 다익스트라 알고리즘은 O(E * Log V) 의 시간 복잡도를 가진다.
아래 내용에서는 각 알고리즘의 특징과 방법을 정리하고 C++ 코드로 구현했다. (간선과 가중치 형태 입력, 인접 리스트)
다익스트라(Dijkstra) 알고리즘 - O(N2)
그래프 사이에 가중치가 존재할 경우 경로를 갱신해가며 한 정점에서 다른 정점까지의 하나의 정점을 기준으로 각 노드의 최단 거리를 알 수 있다. 다익스트라 알고리즘은 양의 가중치를 가진 그래프에서 O(N2)의 시간 복잡도를 갖는다.
아래와 같은 그래프가 있을 때 A에서 각 정점까지의 최단거리를 위의 알고리즘을 따라서 계산해보자.
1. 시작 노드는 A
2. 현재 노드를 기준으로 각 노드의 최소 비용을 계산
최초에 A에서 시작노드를 제외한 각 정점까지의 거리는 INF(무한)로 초기화되어 있기 때문에
A에서 각 정점까지의 최단 거리는 인접한 정점의 거리로 갱신된다.
(1) - 3. 방문 하지 않은 노드 중 최소 비용의 노드를 선택
A에 인접한 노드 중 방문하지 않은 최소 비용의 노드는 E이다.
(1) - 4. 선택된 노드를 기준으로 거리 비용을 계산하여 더 가까울 경우 갱신
E를 기준으로 최소 비용을 계산하면 아래와 같고, 이 때 E를 거쳐 갈 수 있는 경로가 없으므로 갱신하지 않는다.
5. 3~4를 반복하여 모든 노드를 방문
모든 노드를 방문하지 않았으므로 3~4를 반복한다.
(2) - 3. 방문 하지 않은 노드 중 최소 비용의 노드를 선택
E에 인접한 노드 중 방문하지 않은 최소 비용의 노드는 없으므로, A에 인접했던 노드 중 최소 비용의 방문하지 않은 노드인 C 노드를 선택한다.
(2) - 4. 선택된 노드를 기준으로 거리 비용을 계산하여 더 가까울 경우 갱신
C 노드를 지나가는 경로 중 기존의 거리보다 가까운 경우는 D와 F 노드로 가는 경로이다.
해당 값들을 갱신해준다.
(3) - 3. 방문 하지 않은 노드 중 최소 비용의 노드를 선택
C 노드의 인접 노드 중 방문하지 않은 최소 비용 노드는 D이다.
(3) - 4. 선택된 노드를 기준으로 거리 비용을 계산하여 더 가까울 경우 갱신
D 노드를 지나가는 경로 중 기존의 거리보다 가까운 경우는 F 노드로 가는 경로이다.
A-D의 최소 거리인 3과 D-F의 거리인 2를 더하면 5로 기존의 6보다 가깝다.
(4) - 3. 방문 하지 않은 노드 중 최소 비용의 노드를 선택
D 노드의 인접 노드 중 방문하지 않은 최소 비용 노드는 F이다.
(4) - 4. 선택된 노드를 기준으로 거리 비용을 계산하여 더 가까울 경우 갱신
F 를 거쳐 B로 가는 비용 8과 E로 가는 비용 11은 기존 거리보다 멀기 때문에 갱신하지 않는다.
(5) - 3. 방문 하지 않은 노드 중 최소 비용의 노드를 선택
F 노드의 인접 노드 중 방문하지 않은 최소비용 노드는 B이다.
(5) - 4. 선택된 노드를 기준으로 거리 비용을 계산하여 더 가까울 경우 갱신
B 를 거쳐 C 로 가는 경로의 거리 4는 기존 거리보다 멀기 때문에 갱신하지 않는다
6. 탐색 종료
모든 노드와 경로를 방문하였기 때문에 탐색을 종료한다.
A 노드에서 나머지 다른 노드로 가는 과정을 하나의 표로 나타내면 아래의 그림과 같고, 위 그래프에서의 다익스트라 결과는 0 3 2 3 1 5 이다.
이제 위의 과정을 C++ 코드로 구현 해보자.
#include <iostream>
#include <utility>
#include <vector>
#include <cstring>
using namespace std;
int main() {
int n, m, start, max = 99999999;
int min = max, current;
int u, v, a;
cin >> n >> m;
// 방문 여부 초기화
int* visit = new int[n+1];
memset(visit, 0, sizeof(int) * (n+1));
int* d = new int[n];
for (int i = 0; i < n; i++) {
d[i] = max;
}
// 인접 리스트 형태로 입력
vector<pair<int, int>>* adjlist = new vector<pair<int, int>>[n];
cin >> start;
// 노드의 번호(A:1)를 인덱스로 변경(1->0)
if(start > 0) start--;
d[start] = 0;
// 입력
for (int i = 0; i < m; i++) {
cin >> u >> v >> a;
adjlist[u - 1].push_back({ v - 1, a });
}
// 시작노드의 인접 노드 거리로 갱신
for (auto tmp : adjlist[start]) {
d[tmp.first] = tmp.second;
}
// 시작 노드 방문 처리
visit[start] = 1;
// 다익스트라 시작
for (int i = 0; i < n - 1; i++) {
min = max;
current = 0;
// 현재 최단 거리 중 방문하지 않은 노드의 인덱스와 거리를 찾는다.
for (int j = 0; j < n;j++) {
if (d[j] < min && !visit[j]) {
min = d[j];
current = j;
}
}
// 찾은 노드를 방문 처리
visit[current] = 1;
// 현재 노드의 인접 노드 중 방문하지 않은 노드의 거리를 비교하여 갱신
for (auto cur : adjlist[current]){
if (!visit[cur.first]) {
if (d[current] + cur.second < d[cur.first]) {
d[cur.first] = d[current] + cur.second;
}
}
}
}
// 최종 결과 출력
for (int i = 0; i < n; i++) {
cout << d[i] << " ";
}
cout << "\n";
return 0;
}
우선순위 큐 다익스트라(Dijkstra) 알고리즘 - O(N log N)
위의 코드에서는 거리를 비교하고 갱신하기 전에 방문하지 않은 노드 중 최단 거리인 노드를 확인하여 가장 짧은 거리를 선택하도록 했다. 하지만 같은 내용을 매번 반복하였기 때문에 알고리즘의 시간복잡도가 늘었다.
최초 알고리즘이 나온 이후 이런 부분을 개선한 다익스트라 알고리즘이 공개되었는데, 우선순위 큐의 특성을 활용한 다익스트라 알고리즘이다.
우선 순위 큐는 항상 우선순위가 높거나 낮은 값을 pop한다. (우선순위 큐는 시간복잡도가 삽입/삭제 시 항상 O(log N)인 최소힙과 최대 힙을 이용하여 주로 구현된다고 한다. 우선순위 큐를 직접 구현하고 싶다면 https://hwan001.tistory.com/199 글을 참고하자.)
C++에서는 우선순위 큐를 직접 구현할 필요가 없다.
STL을 통해 해당 자료구조를 제공하기 때문인데, priority_queue 타입을 사용하면된다.
해당 자료형에 대한 내용은 위의 우선순위 큐 글에 남겨두겠다.
코드로 구현해보자.
#include <iostream>
#include <utility>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
void dijkstra_pq(int start, vector<pair<int, int>>* graph, int *d) {
int _current, _next, _distance, _nextDistance;
d[start] = 0;
priority_queue<pair<int, int>> pq;
pq.push({0, start});
while (!pq.empty()) {
_current = pq.top().second;
_distance = -pq.top().first;
pq.pop();
if (d[_current] < _distance)
continue;
for (int i = 0; i < graph[_current].size(); i++) {
_next = graph[_current][i].second;
_nextDistance = _distance + graph[_current][i].first;
if (_nextDistance < d[_next]) {
d[_next] = _nextDistance;
pq.push({-_nextDistance, _next});
}
}
}
}
int main() {
int n, m, start, max = 999999999;
int u, v, a;
cin >> n >> m;
int* d = new int[n];
for (int i = 0; i < n; i++) {
d[i] = max;
}
vector<pair<int, int>>* adjlist = new vector<pair<int, int>>[n];
cin >> start;
for (int i = 0; i < m; i++) {
cin >> u >> v >> a;
adjlist[u - 1].push_back({ a, v - 1 });
}
dijkstra_pq(start-1, adjlist, d);
for (int i = 0; i < n; i++) {
if (d[i] == max) {
cout << "INF ";
}
else {
cout << d[i] << " ";
}
}
cout << "\n";
return 0;
}
'코딩테스트 > 알고리즘' 카테고리의 다른 글
| JSON Parsing (0) | 2023.03.19 |
|---|---|
| [알고리즘] 순열과 조합 (0) | 2022.04.21 |
| [자료구조] 우선순위 큐 - 작성 중 (0) | 2022.04.11 |
| [알고리즘] 하노이의 탑 (0) | 2022.03.09 |
| [알고리즘] DFS/ BFS (0) | 2022.02.05 |
| [알고리즘] 달팽이 배열 채우기 (0) | 2021.11.06 |
댓글