[알고리즘] 최단 경로 알고리즘 - 다익스트라(Dijkstra)

안녕하세요, 여행벌입니다.

오늘은 가장 대표적인 최단 경로 알고리즘인 다익스트라(Dijkstra) 알고리즘에 대해서 포스팅해보겠습니다.

---

최단 경로 알고리즘

 최단 경로 알고리즘은 크게 단일 시작점 알고리즘과 모든 쌍 알고리즘으로 나뉩니다. 단일 시작점 알고리즘은 지난 포스팅에서 다뤘던 BFS 탐색과 비슷하게 하나의 시작점에서 다른 모든 정점까지 가는 최단 거리를 구해줍니다. 반면에 모든 쌍 알고리즘은 모든 정점의 쌍에 대해 최단 거리를 계산해줍니다. 단일 시작점 알고리즘으로 가장 유명하고 대표적인 알고리즘이 다익스트라 알고리즘입니다. 즉, 다익스트라 알고리즘을 통해 우리는 시작 정점에서 다른 모든 정점까지 가는 최단 거리를 구할 수 있습니다.

다익스트라 알고리즘

 다익스트라 알고리즘의 작동 원리는 간단합니다. 시작 정점에서부터 아직 방문하지 않은 정점 중 거리가 가장 가까운 정점을 찾습니다. 이때, 거리가 가장 가까운 정점 B를 찾는 방법은 현재까지 방문한 정점 집합에서 거리가 가장 가까운 정점을 찾습니다. 그 후, 다른 모든 정점에 대해서 현재 시작 정점과의 최단 거리와 새롭게 찾은 정점 B를 거쳐서 가는 거리를 비교해서 새롭게 최단 거리를 갱신합니다.

 쉽게 표현하면 A -> C 로 가는 현재 최단 거리와 A -> B -> C 로 가는 거리를 비교해서 최단 거리를 갱신해나갑니다.

● 다익스트라 알고리즘은 시작 정점에서 다른 모든 정점까지의 최단 거리를 저장하는 dist 배열과 방문한 정점에 대해서 기록하는 visited 배열이 필요합니다.

● 간선이 존재하지않는 정점과 정점은 가중치를 INF(매우 큰 값)으로 초기에 설정해놓아야합니다.

● 음수 간선이 존재하는 경우, 최단 거리를 구할 수 없습니다.

 

 그럼, 예시를 통해 다익스트라 알고리즘의 작동 원리를 알아보겠습니다.

다익스트라 알고리즘 코드 구현 (C)

// graph에는 간선이 존재하면 가중치가, 간선이 존재하지않으면 INF가 저장되어있다.
int graph[MAX_VERTICES][MAX_VERTICES];
int distance[MAX_VERTICES];
bool visited[MAX_VERTICES];

void dijkstra(int start) {
	// 초기화 작업 
	for (int i = 0; i < MAX_VERTICES; i++)
		distance[i] = graph[start][i], found[i] = false;
	found[start] = true;
	distance[start] = 0;
	// 가장 가까운 정점부터 탐색을 진행하자.
	for (int i = 0; i < MAX_VERTICES - 1; i++) {
		// 현재 시점에서 방문하지 않은 정점 중 가장 가까운 정점을 찾는다.
		int u = 0, minC = INF;
		for (int j = 0; j < MAX_VERTICES; j++) {
			if (!found[j] && distance[j] < minC)
				u = j, minC = distance[j];
		}
		found[u] = true;
		// 정점을 추가해서 dist 배열을 갱신하자.
		for (int j = 0; j < MAX_VERTICES; j++) {
			if (!found[j] && distance[u] + graph[u][j] < distance[j])
				distance[j] = distance[i] + graph[i][j];
		}
	}
}

 먼저, 현재 그래프의 상태를 담고 있는 graph 배열은 간선이 존재하면 해당 가중치 값을, 아니라면 INF 값으로 셋팅이 되어있어야합니다. 그 후, 시작 정점(S)에서 탐색하지 않은 정점 중 가장 가까운 정점(U)을 찾고, 나머지 모든 정점(W)에 대해서 U를 거쳐서 가는 것이 더 작다면 distance 를 갱신해줍니다.

 즉, distance[W] = min(distance[W], distance[U] + graph[U][W]); 가 성립합니다.

다익스트라 알고리즘 코드 구현 (C++)

vector<pair<int, int>> graph[MAX_VERTICES];

void dijkstra(int start) {
	// distance 배열을 선언하고 INF로 초기화합니다.
	vector<int> distance(MAX_VERTICES, INF);
	vector<bool> visited(MAX_VERTICES, false);

	distance[start] = 0;
	visited[start] = true;
	while (1) {
		int closest = INF, here;
		for(int i = 0; i < MAX_VERTICES; i++)
			if (!visited[i] && distance[i] < closest) {
				here = i;
				distance[i] = closest;
			}
		if (closest == INF) break;  
		// 가장 가까운 점 방문
		for (int i = 0; i < graph[here].size(); i++) {
			int next = graph[here][i].first;
			if (visited[next]) continue;
			int nextDist = distance[here] + graph[here][i].second;
			distance[next] = min(distance[next], nextDist);
		}
	}
}

우선순위 큐를 이용한 다익스트라

 자료구조 우선순위 큐를 이용하면 위에서 구현한 다익스트라 알고리즘보다 효율적인 다익스트라 알고리즘을 구현할 수 있습니다. 우선순위 큐를 이용한 다익스트라 알고리즘은 BFS 탐색과 굉장히 유사합니다.

 우선순위 큐에 정점 번호와 함께 지금까지 찾아낸 해당 정점까지의 최단 거리를 쌍으로 넣습니다. 우선순위 큐는 정점까지의 최단 거리를 기준으로 정점을 배열함으로써, 아직 방문하지 않은 정점 중 시작점으로부터의 거리가 가장 가까운 점을 찾는 과정을 간단하게 해 줍니다.

 따라서, 우리는 우선순위 큐에서 현재 가장 가까운 정점을 뽑을 수 있습니다. 이때, 현재 해당 정점까지 구해놓은 최단 거리가 우선순위 큐에서 뽑은 값보다 더 작다면 이 경우는 갱신할 필요가 없으므로 무시합니다. 이렇게 구현하면 visited 배열을 따로 선언하지 않아도 됩니다.

 그 후, 현재 정점에서 연결된 다른 정점들로 탐색을 진행하가며 dist 배열을 갱신하고, dist 배열이 갱신된 경우는 새로운 최단 거리를 찾았다는 뜻이므로 다시 우선순위 큐에 넣어줍니다. 

우선순위 큐는 기본적으로 내림차순 기준인 Max Heap으로 구현되므로 가중치를 음수로 바꾸어 진행하면 됩니다. 나머지 과정은 따로 진행하지 않겠습니다.

우선순위 큐를 이용한 다익스트라 알고리즘 코드 구현 (C++)

 C++ STL 에서 지원해주는 우선순위 큐를 이용하면 손쉽게 구현할 수 있습니다. 이때, 우리는 거리가 짧은 정점을 큐에서 뽑아내고 싶으므로, 큐에 ( -최단거리, 정점 번호 ) 를 쌍으로 넣습니다.

#include<vector>
#include<queue>
using namespace std;

#define MAX_VERTICES 100
#define INF 987654321
vector<pair<int, int>> graph[MAX_VERTICES];

void dijkstra(int start) {
	// distance 배열을 선언하고 INF로 초기화합니다.
	vector<int> distance(MAX_VERTICES, INF);
	distance[start] = 0;
	priority_queue<pair<int, int>> pq;
	pq.push({ 0, start }); 
	while (!pq.empty()) {
		int cost = -pq.top().first;
		int here = pq.top().second;
		pq.pop();
		// 지금 꺼낸 것보다 더 짧은 경로를 알고 있다면 무시한다.
		if (distance[here] < cost) continue;
		// 인접한 정점들을 검사하며 경로 갱신!
		for (int i = 0; i < graph[here].size(); i++) {
			int next = graph[here][i].first;
			int nextDist = cost +  graph[here][i].second;
			// 현재 정점을 거쳐서 이동하면 최단 거리가 갱신되는 경우
			if (nextDist < distance[next]){
				distance[next] = nextDist;
				pq.push({ -nextDist, next });
			}
		}
	}
}

다익스트라 알고리즘 시간 복잡도

* 정점의 개수 V , 간선의 개수 E *

 우선순위 큐를 이용하지 않은 다익스트라 알고리즘은 정점이 V개 있을 때, 시작 정점을 제외한 모든 정점에 대해서, 가장 가까운 점을 찾고, 최단 거리를 갱신해주는 과정을 거치므로 O(V^2 + E) 의 시간 복잡도를 가지게 됩니다.

 하지만, 우선순위 큐를 이용해 다익스트라 알고리즘을 구현하게 된다면 시간 복잡도를 줄일 수 있습니다.

 먼저 우선순위 큐에 추가되는 원소의 수는 최대 E(간선의개수)개 이므로 O(logE) 의 시간이 걸립니다. 또, E개의 원소에 대해 이 작업을 진행해야하므로 O(E * logE)의 시간 복잡도를 가지는 것을 알 수 있습니다.

 보통, E는 V^2 보다 작기 때문에 O(E * logV) 로 시간 복잡도를 표기할 수 있습니다.

---