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

안녕하세요. 옆집 컴공생입니다. 오늘은 다익스트라 알고리즘을 배워볼거예요.

다익스트라(Dijkstra Algorith)은 다이나믹 프로그래밍을 활용한 대표적인 최단경로(Shortest Path) 탐색 알고리즘입니다. 흔히 인공위성 GPS 소프트웨어등에 많이 이용된다고 하네요. 음의 간선을 포함할 수 없는데 현실에는 음의 간선이란 게 존재하지 않잖아요? 그러니깐 매우 현실적인 알고리즘 중 하나라고 할 수 있겠습니다.

 

다익스트라 알고리즘은 다이나믹 프로그래밍이나 그리디 알고리즘을 분류가 되는데요. 다이나믹 프로그래밍인 이유는 이러합니다. '최단거리는 여러 개의 최단거리로 이루어져 있다.' 너무 당연하게도, A -> B -> C -> D 로 가는 최단 걸이로 가는데 A -> C -> B 가 A -> B -> C 보다 짧으며 전체가 최단거리일 수 없겠죠. 그러므로 작은 문제가 큰 문제의 부분 집합에 속해있다고 판단하는 겁니다. 기본적으로 그 전에 구했던 최단 거리 정보를 그대로 사용한다는 특징이 있습니다. 이 부분도 다이나믹 프로그래밍이기 때문에 그런거죠? 그리고 정렬 후 가장 최단거리인 노드를 선택하기 때문에 그리디 알고리즘이라고 불리기도 합니다. 

 

간단하게 그림을 볼까요?

현재 노드 1과 연결되어 있는 노드는 2,3,4 로 최단거리를 1,3,5로 설정할 수 있습니다. 이건 '현재 1에서 4로 가는 최단거리가 5'라는 걸 기억하는 겁니다. 그 후 다음 노드인 2로 가 볼까요? 1 -> 2 -> 4 로 가면 거리가 1 + 2 = 3 입니다. 그럼 1에서 4로 가는 최단 거리가 3으로 갱신이 되는겁니다. 다익스트라 알고리즘은 이런 식으로 최단 경로를 계속해서 갱신해주는 겁니다. 

 

작동과정은 다음과 같습니다.

1. 출발 노드 설정

2. 출발 노드 기준으로 각 노드의 최소 비용 저장

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

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

5. 3번 ~ 4번 반복

 

 

바로 예제를 보도록 합시다. 원래 예제를 보면서 해야 이해가 빠르니깐요!

 이 그래프는 컴퓨터 안에서 2차원 배열을 사용해야 합니다. 가로가 행이고 세로가 열입니다.(늘 헷갈려요) 다음 보는 특정 행에서 열로 가는 비용을 나타내고 있습니다. 

0	2	5	1	무한	무한
2	0	3	2	무한	무한
5	3	0	3	1	5
1	2	3	0	1	무한
무한	무한	5	1	0	2
무한	무한	5	무한	2	0

연결이 되어 있지 않은 노드는 무한입니다.  2행에서 3열 노드를 보면 3이죠? 이는 2에서 3까지 가는데의 비용이 3이 든다는 말입니다. 

 

그럼 선택 노드를 1로 하고 시작해보겠습니다. 방문 안 한 노드 중 가장 작은 노드는 1로 4 입니다. 4번 노드를 선택해 줍니다. 그럼 이 4번 노드를 거쳐서 가는 경우를 모두 고려하여 최소 비용 배열을 갱신하면 됩니다. 

0

2

5

1

무한

무한

 

 

기존에 5로 가는 게 4를 거쳐서 가면 2로 갈 수 있습니다. 3도 4를 걸쳐가면 5에서 4로 줄어듭니다. 그리고 방문노드 처리를 해줍니다. 

0

2

4

1

2

무한

 

 

 

다음 방문할 노드는 2입니다. 5도 가깝지만 인덱스 상으로 더 빠르기 때문입니다. 보면 갱신할 노드가 없습니다. 

0

2

4

1

2

무한

 

 

 

다음으로 방문하지 않은 노드 중에서 가장 비용이 적은 노드는 5입니다. 

5를 걸쳐가면 1에서 3으로 가는데 3의 비용이 듭니다. 또 노드 6으로도 갈 수 있습니다.

0

2

3

1

2

4

 

 

 

방문하지 않은 노드 중 가장 작은 3번째 노드를 골라줍니다. 최소비용 값 갱신이 일어나지 않았습니다.

0

2

3

1

2

4

 

 

 

마지막으로 남은 노드 6을 봅니다.  갱신이 일어나지 않았습니다.

0

2

3

1

2

4

 

 

 

이렇게 모든 노드를 방문했습니다. 

 

 

 

#include <stdio.h>

int number =6;
int INF = 1000000000;

//전체 그래프 초기화

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]; //start 노느의 인접 노드와의 거리 
	}
	v[start] = true; //start 노드 방문처리 
	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(void){
	dijkstra(0);
	for(int i =0;i < number; i++){
		printf("%d ", d[i]);
	}
}

 

 

위의 코드는 이해하기가 쉽지만 선형 탐색으로 참기 때문에 시간 복잡도가 O(N^2) 입니다. 다익스트라 반복문에 있는 getSmallIndex() 도 반복문이 있기 때문입니다. 그렇기 때문에 힙 구조를 활용해서 시간복잡도를 O(NlogN)으로 만들어보겠습니다. 특히 위의 코드는 노드는 많은데 간선이 적을때 굉장히 치명적이라고 합니다.

 

 

#include <iostream>
#include <vector>
#include <queue>//우선순위힙을 사용하기 위해 

using namespace std;
 
 
int number = 6;
int INF = 100000000;

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(void){
	//기본적으로 연결되지 않은 경우 비용은 무한
	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++){
		printf("%d ",d[i]);
	}
}

 

이렇게 다익스트라 알고리즘을 마치겠습니다. 

 

 

※이 글은 나동빈님의 블로그를 보고 작성이 된 겁니다. 

https://blog.naver.com/ndb796/221234424646

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