다익스트라 알고리즘(Dijkstra Algorithm)

다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘입니다.

 

다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 다만 이 때 음의 간선을 포함할 수 없다.

 

다익스트라 알고리즘이 다이나믹 프로그래밍 문제인 이유는 '최단 거리는 여러개의 최단 거리로 이루어져있기 때문이다' 작은 문제가 큰 문제의 부분 집합에 속해있다고 볼 수 있다. 기본적으로 다익스트라는 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다는 특징이 있다.

 

다시 말해 다익스트라 알고리즘은 '현재까지 알고 있던 최단 경로를 계속해서 갱신'합니다.

 

1. 출발 노드를 설정합니다.

2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장합니다.

3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택합니다.

4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신합니다.

5. 위 과정에서 3번 ~ 4번을 반복합니다.

 

 

 

선형 탐색을 이용한 다익스트라 알고리즘.

#include <iostream>
using namespace std;

int number = 6;
int INF = 100'000'000;

// 전체 그래프를 초기화
int a[6][6] = {
	{0, 2, 5, 1, INF, INF},
	{2, 0, 3, 2, INF, INF},
	{5, 3, 0, 3, 1, 5},
	{1, 2, 3, 0, 1, INF},
	{INF, INF, 1, 1, 0, 2},
	{INF, INF, 5, INF, 2, 0},
};

bool v[6]; // 방문한 노드
int d[6]; // 최단 거리

// 가장 최소 거리를 가지는 정점을 반환합니다.
int getSmallIndex() {
	int min = INF;
	int index = 0;
	
	for(int i = 0; i < number; i++) {
		if(d[i] < min && !v[i]) {
			min = d[i];
			index = i;
		}
	}
	return index;
}

// 다익스트라를 수행하는 함수입니다.
void dijkstra(int start) {
	for(int i = 0; i < number; i++) {
		d[i] = a[start][i];
	}
	v[start] = true;
	
	for(int i = 0; i < number - 2; i++) {
		int current = getSmallIndex();
		v[current] = true;
		for(int j = 0; j < 6; j++) {
			if(!v[j]) {
				if(d[current] + a[current][j] < d[j]) {
					d[j] = d[current] + a[current][j];
				}
			}
		}
	}
}

int main() {
	dijkstra(0);
	
	for(int i = 0; i < number; i++) {
		cout << d[i] << endl;
	}
	return 0;
}

하지만 이렇게 선형탐색을 이용한 작성하게 되면 O(N^2)을 형성하게 된다. 그렇게 되면 다양한 문제에서 시간초과를 유발 할 수 있다. 이럴 경우 단축을 하기 위해서는 힙을 이용하는 방법이 있다.

 

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

int number = 6;
int INF = 100'000'000;

vector<pair<int, int>> a[7]; // 간선 정보
int d[7]; // 최소 비용

void dijkstra(int start) {
	d[start] = 0;
	priority_queue<pair<int, int>> pq; // 힙 구조입니다.
	pq.push(make_pair(start, 0));
	
	// 가까운 순서대로 처리하므로 큐를 사용합니다.
	while(!pq.empty()) {
		int current = pq.top().first;
		// 짧은 것이 먼저 오도록 음수화(-) 합니다.
		int distance = -pq.top().second;
		pq.pop();
		
		// 최단 거리가 아닌 경우 스킵합니다.
		if(d[current] < distance) continue;
		for(int i = 0; i < a[current].size(); i++) {
			// 선택된 노드의 인접 노드
			int next = a[current][i].first;
			
			// 선택된 노드 거쳐서 인접 노드로 가는 비용
			int nextDistance = distance + a[current][i].second;
			
			// 기존의 비용보다 더 저렴하다면 교체합니다.
			if(nextDistance < d[next]) {
				d[next] = nextDistance;
				pq.push(make_pair(next, -nextDistance));
			}
		}
	}
}

int main() {
	for(int i = 1; i <= number; i++) {
		d[i] = INF;
	}
	a[1].push_back(make_pair(2, 2));
	a[1].push_back(make_pair(3, 5));
	a[1].push_back(make_pair(4, 1));
	
	a[2].push_back(make_pair(1, 2));
	a[2].push_back(make_pair(3, 3));
	a[2].push_back(make_pair(4, 2));
	
	a[3].push_back(make_pair(1, 5));
	a[3].push_back(make_pair(2, 3));
	a[3].push_back(make_pair(4, 3));
	a[3].push_back(make_pair(5, 1));
	a[3].push_back(make_pair(6, 5));
	
	a[4].push_back(make_pair(1, 1));
	a[4].push_back(make_pair(2, 2));
	a[4].push_back(make_pair(3, 3));
	a[4].push_back(make_pair(5, 1));
	
	a[5].push_back(make_pair(3, 1));
	a[5].push_back(make_pair(4, 1));
	a[5].push_back(make_pair(6, 2));
	
	a[6].push_back(make_pair(3, 5));
	a[6].push_back(make_pair(5, 2));
	
	dijkstra(1);
	
	for(int i = 1; i <= number; i++) {
		cout << d[i] << endl;
	}
}

음수화를 사용하는 이유는 priority_queue 같은 경우 최대 힙으로 구성되어 있기 때문에 음수화를 통해 최소 힙의 형태를 이루게 만들려는 목적이다.