다익스트라 알고리즘

안녕하세요.

 

최근 PS 관련 풀이를 하던도중 다익스트라 알고리즘에 대해 접하게 되었는데요.

 

사실 학부시절때 이론은 수업을 들어서 알고 있었지만 깊게 공부해보지 않아서 코드로 적용하기가 힘들더라구요...

 

그래서 이번 기회에 조금 깊게 공부해본 내용을 설명 하게 되었습니다.

 

●다익스트라 알고리즘 요약

• 1956년에 에즈허르 데이크스트라가 고안
• 다익스트라 알고리즘은 두 꼭지점 사이의 최단 경로 거리를 구하는 알고리즘
• 방향성 그래프와 무방향성 그래프 모두에 적용가능
• 가중치가 음수이면 사용 불가능
• 현제 길찾기 알고리즘의 기초가 되는 알고리즘

 

최초의 다익스트라는 출발노드를 기준으로 최소비용 그래프를 저장하여 방문하지 않은 노드 중 가장 가까운 거리에 있는 노드를 먼저 방문을 한 후 또 다른 노드를 방문하게 될 때 기존에 알고 있던 최단 경로보다 가까울 경우 그래프를 갱신하는 방법으로 제시 되었습니다.

 

코드

connect 벡터에 간선의 연결정보가 들어있다는 가정하에 최단거리 그래프를 만드는 코드입니다.

해당 코드는 노드에 비해 간선이 많이 적을 경우 치명적으로 비효율적으로 작용합니다.

#include<iostream>
#include<vector>
#define INF 987654321
#define N 10
using namespace std;

vector<pair<int,int>> connect_info[N];
// <간선, 가중치>를 가지는 연결정보

void Dijkstra(int start)
{
	vector<int>node_dist(N, INF);
	//current 노드의 최단거리 그래프가 저장될 벡터 배열
	vector<bool>visited(N, false);
	//노드의 방문 여부를 저장할 벡터 배열


	node_dist[start] = 0;
	visited[start] = true;
	//start 노드에 대한 처리
	while (true)
	{
		int current;
		int closest_dist = INF;
		
		for (int i = 0; i < N; i++)
		{
			if (node_dist[i] < closest_dist && !visited[i])
			{
				current = i;
				closest_dist = node_dist[i];
			}
		}
		//방문하지 않은 노드중 최단거리 노드를 찾는다.

		if (closest_dist == INF) break;
		//연결되어 있는 노드를 모두 방문 했을경우 탈출

		visited[current] = true;
		for (int i = 0; i < connect_info[current].size(); i++)
			//current 노드와 연결되어 있는 노드를 모드방문
		{
			int next = connect_info[current][i].first;

			if (visited[next]) continue;
			
			int next_dist = connect_info[current][i].second;
			if (node_dist[next] > next_dist + node_dist[current])
				//기존에 가지고 있는 거리보다 가까울 경우 갱신
			{
				node_dist[next] = next_dist + node_dist[current];

			}
		}
	}
}

시간복잡도

 최초 다익스트라는 한 노드로부터 방문하지 않은 모든 노드(N)를 방문하여 또 다른 방문하지 않은 모든 노드(N)를 방문을 하기때문에 시간 복잡도는 O(N^2)를 가지게 됩니다.

 

다음은 우선순위 큐를 이용해서 개선이 된 다익스트라를 소개 해드리겠습니다.

 

코드

#include<iostream>
#include<vector>
#define INF 987654321
#define N 10
using namespace std;

vector<pair<int, int>> connect_info[N];
// <간선, 가중치>를 가지는 연결정보

void Dijkstra(int start) {
	vector<int> node_dist(N, INF);
	node_dist[start] = 0;
	priority_queue<pair<int, int> > p_q;
	p_q.push(make_pair(0, start));

	while (!p_q.empty()) {
		int current_dist = -p_q.top().first;
		int current = p_q.top().second;
		p_q.pop();

		if (node_dist[current] < current_dist) continue;
		//현제 방문한 노드가 가지고있는 최소거리보다 큰 가중치를 가졌으면 확인하지 않음

		
		for (int i = 0; i < connect_info[current].size(); ++i) 
			// 해당 노드에서 인접한 정점들을 모두 확인
		{
			int next = connect_info[current][i].first;
			int next_dist = connect_info[current][i].second;
			// 더 짧은 경로를 발견하면, node_dist를 갱신하고 
            // 다음 확인대상에 추가하기위해 우선순위 큐에 넣음
			if (node_dist[next] > next_dist + current_dist) {
				node_dist[next] = next_dist + current_dist;
				p_q.push(make_pair(-node_dist[next], next));
			}
		}
	}
}

우선순위 큐를 적용한 코드를 확인 해보면 가중치를 추가할떄 부호(-)를 변경해서 넣게 됩니다.

우선순위 큐는 높은 값을 위쪽으로 정렬하기 때문에 가중치가 낮은 간선부터 확인해 나갈 수 있게됩니다.

 

시간복잡도

각 노드에서 자신을 제외하고 가질 수 있는 최대 노드의 수(E 간선) 만큼 우선 큐를 적용시켜야합니다. (O(E))

그리고 우선큐가 추가하거나 삭제하는 시간은 O(logE)로 나타낼 수 있기 때문에 전체 시간 복잡도는 O(ElogE)로 나타낼 수 있습니다.