[알고리즘] 데이크스트라 알고리즘 (Dijkstra Algorithm)

데이크스트라 알고리즘 (Dijkstra Algorithm)

 

데이크스트라 알고리즘은 그래프에서 정점 간의 최단 경로를 찾는 탐색 알고리즘입니다. 예를 들어 여러 개의 도시가 있을 때 도시 사이를 연결하는 도로의 길이를 최소 비용으로 계산하여 건설하고자 할 때와 같이 현실 세계의 다양한 상황에서 사용될 수 있는 알고리즘입니다.

 

또한 그래프 내에서 하나의 최단 경로는 다른 여러 최단 경로로 만들어질 수 있으므로 기존에 저장되었던 최단 경로의 결괏값이 그대로 사용될 수 있다는 점에서 다이나믹 프로그래밍을 적용하여 사용할 수 있습니다.

 

알고리즘 원리

위 그림에서 정점 1로부터 정점 2, 3, 4로의 최단 경로가 각각 5, 9, 13으로 설정되어 있습니다. 

정점 1은 방문이 완료되었으므로 다음으로 가장 가까운 정점 2를 방문합니다.

하지만 정점 2를 방문하게 되는 순간 정점 1에서 정점 2를 통해 정점 3으로 가는 최단 경로가 7인 것을 발견하여 정점 1에서 정점 3으로의 직접 간선에 비해 경로가 더 짧다는 것을 찾게 되고 정점 1에서 정점 3으로의 최단 경로를 9에서 7로 새롭게 설정합니다.

 

따라서 기본적인 알고리즘은 다음과 같습니다.

1. 시작 정점을 설정한다.

2. 시작 정점으로부터 직접 간선으로 연결된 정점들 사이의 최단 경로를 저장한다.

3. 방문하지 않은 정점 중 최단 경로의 정점을 선택한다.

4. 선택된 정점을 통해 특정한 정점까지의 경로를 고려해 최단 경로를 새롭게 설정한다.

5. 3과 5의 과정을 반복한다.

위 그래프와 같은 예시로 데이크스트라 알고리즘을 통해 탐색해보겠습니다. 시작 정점은 정점 1이며 아래 표는 각 정점사이의 경로를 나타낸 것입니다. 예를 들어 정점 1에서 정점 2까지의 거리는 6이며 정점 2에서 정점 4까지의 거리는 14입니다. INF는 무한을 의미하며 아직 경로가 정해지지 않은 정점 사이를 INF로 설정합니다.

정점1	정점2	정점3	정점4	정점5	정점6
0	6	8	INF	INF	13
6	0	9	14	INF	INF
8	9	0	10	INF	1
INF	14	10	0	5	INF
INF	INF	INF	5	0	8
13	INF	1	INF	8	0

 

정점 1부터 탐색을 시작합니다.

0

6

8

INF

INF

13

정점 1이 방문되었고 직접 간선 3개를 확인합니다. 이 중 경로가 가장 적은 정점 2를 방문할 것입니다. 

0

6

8

20

INF

13

정점 2가 방문되었고 정점 1에서 4로의 경로가 INF에서 20으로 새롭게 설정됩니다. 정점 1에서 정점 2를 통해 정점 3으로가는 경로가 15로 발견되었지만 기존 경로인 8이 더 적으므로 새로 설정되지 않습니다. 그 다음으로 가장 경로가 적은 정점 3을 방문합니다

0

6

8

18

INF

9

정점 3이 방문되었고 새롭게 설정된 경로가 2가지입니다. 정점 1에서 정점 6으로 가는 경로(13)가 정점 1에서 정점 3을 통해 정점 6으로 가는 경로(9)가 더 적은 것을 발견하여 경로를 9로 새로 설정합니다.

마찬가지로 정점 1에서 정점 4로가는 경로 역시 정점 3을 거쳐간 경로(18)가 더 적으므로 18로 새로 설정합니다.

그 다음으로 경로가 가장 적은 정점 6을 방문합니다

0

6

8

18

17

9

정점 6이 방문되었고 정점 1에서 정점 5로의 경로가 기존 INF에서 정점 3과 정점 6을 통한 17로 새로 설정됩니다.

그 다음으로 경로가 가장 적은 정점 5를 방문합니다.

0

6

8

18

17

9

정점 5가 방문되었고 새로 설정되는 경로는 없습니다. 그 다음으로 마지막으로 남은 정점 4를 방문합니다.

0

6

8

18

17

9

모든 정점을 방문하였고 최종적으로 최단 경로가 위와 같이 설정되었습니다.

 

알고리즘 구현 : 원론적

// Algorithm Analysis
// 원론적 데이크스트라 알고리즘 (Dijkstra Algorithm)

#include <iostream>
using namespace std;

int n = 6;
int INF = 1000000000;

int arr[6][6] = {
	{0, 6, 8, INF, INF, 13},
	{6, 0, 9, 14, INF, INF},
	{8, 9, 0, 10, INF, 1},
	{INF, 14, 10, 0, 5, INF}, 
	{INF, INF, INF, 5, 0, 8},
	{13, INF, 1, INF, 8, 0},
};
bool visited[6]; // 방문한 정점
int d[6]; // 최단 경로(비용)

int getMinIndex() {
	int min = INF;
	int idx = 0;
	for (int i = 0; i < n; i++) {
		if (d[i] < min && !visited[i]) {
			min = d[i];
			idx = i;
		}
	}
	return idx;
}
void dijkstra(int start) {
	for (int i = 0; i < n; i++) {
		d[i] = arr[start][i];
	}
	visited[start] = true;
	for (int i = 0; i < n - 2; i++) {
		int minIndex = getMinIndex(); // 현재의 최단 경로 index
		visited[minIndex] = true;
		for (int j = 0; j < 6; j++) {
			if (!visited[j]) {
				if (d[minIndex] + arr[minIndex][j] < d[j]) { // 더 적은 최단 경로를 발견하면
					d[j] = d[minIndex] + arr[minIndex][j]; // 경로를 새롭게 설정
				}
			}
		}
	}
}
int main() {
	dijkstra(0);
	for (int i = 0; i < n; i++) {
		cout << d[i] << " ";
	}
}
// 0 6 8 18 17 9

데이크스트라 알고리즘은 원론적 형식과 변형된 형식이 존재합니다. 지금까지 알려드린 방식이 데이크스트라 알고리즘의 원론적 형식이며 이 알고리즘은 시간 복잡도가 O(N^2)으로써 특정 문제에서는 비효율적인 문제가 발생합니다. 예를 들어 정점이 무수히 많고 그에 비해 간선은 적은 경우 매우 느리고 비효율적입니다.

 

이를 위해 변형된 데이크스트라 알고리즘은 우선순위 큐의 힙 자료구조를 사용하여 시간 복잡도를 O(N*logN)으로 빠르게 동작시킬 수 있습니다. 

 

알고리즘 구현 : 우선순위 큐 사용

// Algorithm Analysis
// 변형 데이크스트라 알고리즘 (Dijkstra Algorithm)

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n = 6;
int INF = 1000000000;

vector<pair<int, int>> arr[7]; // 정점(first)로 가는 최단 경로(second)
int d[7];

void dijkstra(int start) {
	d[start] = 0; // 자기 자신에 대한 경로는 0
	priority_queue<pair<int, int>> pq;
	pq.push(make_pair(start, 0)); 

	while (!pq.empty()) {
		int cur = pq.top().first; // 현재 정점
		int dist = -pq.top().second; // 최단 경로
		pq.pop();

		if (d[cur] < dist) continue;
		for (int i = 0; i < arr[cur].size(); i++) { // pair가 만들어진 수 만큼
			int next = arr[cur][i].first; // 방문한 정점의 인접 정점
			int nextDist = dist + arr[cur][i].second; // 방문한 정점을 거쳐 인접 정점으로 가는 최단 경로
			if (nextDist < d[next]) { // 기존 경로보다 더 적다면
				d[next] = nextDist; // 새로 설정
				pq.push(make_pair(next, -nextDist)); 
			}
		}
	}
}
int main() {
	for (int i = 1; i <= n; i++) {
		d[i] = INF;
	}
	arr[1].push_back(make_pair(2, 6));
	arr[1].push_back(make_pair(3, 8));
	arr[1].push_back(make_pair(6, 13));

	arr[2].push_back(make_pair(1, 6));
	arr[2].push_back(make_pair(3, 9));
	arr[2].push_back(make_pair(4, 14));

	arr[3].push_back(make_pair(1, 8));
	arr[3].push_back(make_pair(2, 9));
	arr[3].push_back(make_pair(4, 10));
	arr[3].push_back(make_pair(6, 1));

	arr[4].push_back(make_pair(2, 14));
	arr[4].push_back(make_pair(3, 10));
	arr[4].push_back(make_pair(5, 5));

	arr[5].push_back(make_pair(4, 5));
	arr[5].push_back(make_pair(6, 8));

	arr[6].push_back(make_pair(1, 13));
	arr[6].push_back(make_pair(3, 1));
	arr[6].push_back(make_pair(5, 8));

	dijkstra(1);
	for (int i = 1; i <= n; i++) {
		cout << d[i] << " ";
	}
}
// 0 6 8 18 17 9

 

 

* 나동빈님 블로그를 참고하여 개인적으로 재작성한 글입니다.