코딩무식자 전공생

저번에 작성한 다익스트라의 구현1은 선형탐색으로 O(N^2)의 시간복잡도를 가지므로, 최단거리 알고리즘 문제를 풀 때 비효율적일 수 있습니다.

제가 갖고있는 2권의 자료구조책과 한권의 알고리즘책에도 구현의 난이도 때문인지 O(N^2)의 방법만 설명해주고있고, 구글링해본결과  우선순위 큐(힙)를 이용하여 O(NlogN)의 시간복잡도를 가지는 다익스트라의 구현법을 알게되어 직접 구현해보았습니다.정확하게 설명하자면 O(ElogV)입니다.

원리는 선형탐색의 방법과 똑같지만 내부구현방식만 다르고, 우선순위 큐의 구현을 글로 설명하는게 힘들어서 직접 그려보고 이해할 수 있게 저번과 같은 간단한 경우로 구현하였고, 헷갈릴 수 있는 부분은 최대한주석으로 작성해보았습니다.

주의 할 것은 우선순위큐에 삽입 시 거리를 음수화하여 삽입하고 뺄 때도 그 값을 음수화하여(결국 양수) 연산하는것입니다. 직접 그려보면 이해가 쉽습니다.

코드

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int INF = 100000000;
vector<pair<int, int>>a[4];
int d[4];
void dijkstra(int start);
int main()
{
	for (int i = 0; i < 4; i++)
		//최초의 최단거리배열은 무한대로잡아두고시작
		d[i] = INF;
	
	a[0].push_back(make_pair(1, 5));
	a[0].push_back(make_pair(2, 1));

	a[1].push_back(make_pair(0, 5));
	a[1].push_back(make_pair(2, 2));

	a[2].push_back(make_pair(0, 1));
	a[2].push_back(make_pair(1, 2));
	a[2].push_back(make_pair(3, 3));

	a[3].push_back(make_pair(2, 3));
	dijkstra(0);
	for (int i = 0; i < 4; i++)
		cout << d[i] << " ";
	cout << endl;
}
void dijkstra(int start)
{
	//첫 노드와 첫 노드는 최단거리없으므로 0
	d[start] = 0;
	priority_queue<pair<int, int>>pq;
	//우선순위큐의 first는 거리, second는 노드(정점)의미
	pq.push(make_pair(0, start));
	while (!pq.empty())
	{
	
		//설명을 돕기위해 0번(a)노드와 1번(b)노드,2번노드(c)를 예로들겠음
		//어짜피 첫 노드는 distacne=0,current=0이므로
		//0번노드를제외한 최초의 첫 번째 큐삽입연산은68행임 
		//67행에서 a와 맞닿아있는 b와의거리(5)와 c와의거리(1)이 삽입됨
		//이 때, 어떠한 음수의 조건이없다면, (5,1),(1,2)순으로 큐에저장됨
		//최단거리부터 알고 싶으므로 67행을 음수화하여 삽입하면 (-1,2),(-5,1)로 정렬됨
		//그렇기 때문에 47행에서 다시 뽑을 때 음수화하여 뽑으면 최단거리순으로 뽑게됨.
		int distance = -pq.top().first;
		int current = pq.top().second;
		pq.pop();

		//아래처럼 건너뛰는 연산식을 적어야 불필요한 연산을 줄일 수 있음
		//ex)(5,1)가 큐에있는데 3으로 이미 수정되어있으므로 볼필요도없으므로 
		//최단거리가 아니면 스킵한다.
		if (d[current] < distance)
			continue;

		for (int i = 0; i < a[current].size(); i++)
		{
			int next = a[current][i].first;
			//next_distance=0번~현재노드까지의 최단거리(계속 수정됨)+현재노드~탐색할노드의 거리
			int next_distance = distance + a[current][i].second;
			//기존의 최단거리보다 더 작은 값이면 그값으로 갱신
			if (d[next] > next_distance)
			{
				d[next] = next_distance;
				//음수화 삽입
				pq.push(make_pair(-next_distance, next));

			}
		}
	}
}

결과

선형탐색으로 구현한 일반적인 다익스트라 구현방법입니다.

직관적이고, 작성이쉬운 장점이 있으나, 최단거리를구하기위해 짧은거리부터 찾아나가는 연산과 전체적인 다익스트라를 수행하는 연산이 약 n^2번 까지도 돌 수 있으므로 평균 시간복잡도가 O(N^2)입니다.

아래 경우를 예시로 하여 0번노드에서부터의 다익스트라를 구현해보았습니다.

코드

#include<cstdio>
#define INF 21474836

#define MAX_VERTEX 4

int weight[MAX_VERTEX][MAX_VERTEX] =
{
	{0,5,1,INF},
	{5,0,2,INF},
	{1,2,0,3},
	{INF,INF,3,0}
};
bool visited[4];
int d[4];
void dijkstra(int start);
int  small_index();
int main()
{
	dijkstra(0);
	for (int i = 0; i < 4; i++)
		printf("%d ", d[i]);
	puts("");
}
void dijkstra(int start)
{
	for (int i = 0; i < 4; i++)
		d[i] = weight[start][i];
	visited[start] = 1;

	//첫째노드와 마지막 노드에서 최단거리를 구할필요는없으므로
	//i<4가 아닌 i<2
	for (int i = 0; i < 2; i++)
	{
		int current = small_index();
		visited[current] = 1;
		for (int j = 0; j < 4; j++)
		{
			if (!visited[j]) {
				//current까지의최단거리+현재~도착까지의거리<도착까지의최단거리라면,
				if ((d[current] + weight[current][j]) < d[j])
				{
					//작은값으로 갱신
					d[j] = d[current] + weight[current][j];
				}
			}
		}
	}
}
int  small_index()
{
	int min = INF;
	int index = 0;
	for (int i = 0; i < 4; i++) {
		if (d[i] < min && !visited[i])
		{
			min = d[i];
			index = i;
		}
	}
	return index;

}

결과