다익스트라 알고리즘

다익스트라 알고리즘이란?

그래프의 한 정점에서 다른 정점까지의 최단경로를 구하는 알고리즘

 

-시간 복잡도

최소 비용을 구할 때 선형탐색을 사용할 경우 : O(N^2)

최소 비용을 구할 때 힙 구조를 활용할 경우 : O(N*logN)

 

선형 탐색을 할 경우에는 정점의 개수가 많은데 간선의 개수는 적을 때 비효율적이다.

선형 탐색으로 최소 비용을 구함이란 다음을 말한다.

\

노드 1와 이웃한 노드들 중 다음 탐색할 노드를 결정할 때 최소 비용을 가진 노드를 먼저 선택한다. 선형 탐색으로 이를 찾으려면 노드2 -> 노드3 -> 노드4 이렇게 앞에 노드2, 노드3을 거쳐야 노드1과 이웃한 노드들 중 최소 비용인 노드를 찾을 수 있다.

그래서 정점의 개수는 많은데 간선의 개수는 적을 때 최소 비용을 가진 노드를 찾기위해 불필요한 탐색을 많이 거치게 되므로 선형 탐색이 비효율적이라는 것이다.

 

-다익스트라 동작 과정

1. 출발 노드 지정

2. 출발 노드를 기준으로 다른 노드들까지의 비용을 저장

3. 방문하지 않은 노드 & 가장 최소 비용인 노드 선택

4. 출발 노드에서 해당 노드를 거쳐서 다른 노드로 가는 비용 갱신

5. 3번 4번 과정 반복

 

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

#include<stdio.h>

int n=6; //노드 개수 
int INF=10000000;

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},
};
int visit[6]={0}; //방문여부 
int d[6]; //가중치 

//인접 노드 중 최소 비용을 가진 노드 구하기 
int minimumCost(){
	int min=INF;
	int index=0;
	for(int i=0;i<n;i++){
		if(visit[i]==0&&d[i]<min){
			min=d[i];
			index=i;
		}
	} 
	return index;
}

void dijkstra(int start){
	//출발 노드를 기준으로 가중치 저장 
	for(int i=0;i<n;i++){
		d[i]=a[start][i];
	}
	visit[start]=1;
	
	//출발 노드 기준 최소 비용인 노드를 기준으로 가중치 갱신 
	for(int i=0;i<n;i++){
		int current=minimumCost(); 
		visit[current]=1;
		for(int j=0;j<6;j++){
			if(visit[j]==0){
				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<n;i++){
		printf("%d ",d[i]);
	}
}

-힙 구조를 사용한 다익스트라 알고리즘

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

int n=6; //노드 개수 
int INF=10000000;
vector<pair<int,int> >a[7]; //간선 정보 
int d[7]; //최소 비용 
void insert();

void dijkstra(int start){
	d[start]=0;											////d[1]=0
	priority_queue<pair<int,int> >pq; //힙 구조 
	pq.push(make_pair(start,0));                        ////pq={(1,0)}
	
	while(!pq.empty()){
		//큐의 가장 위에는 가장 작은 값의 노드가 있음
		int current = pq.top().first;  //노드           ////pq.top().first=1
		//짧은 것이 먼저 오도록 음수화 (우선순위 큐 pq는 큰 값이 앞에 오는 maxheap구조 인데 난 minheap을 사용하고 싶으므로)
		int distance = -pq.top().second;  //가중치      ////pq.top().second=0
		pq.pop();										////pq={}
		//최단 거리가 아닌 경우 스킵 
		if(d[current]<distance)                         ////d[1] (0) < 0
			continue;
		for(int i=0 ; i<a[current].size() ; i++){       ////a[1].size=3
			//출발 노드의 인접 노드
			int next = a[current][i].first;             ////next=2
			//출발 노드에서 시작해 인접 노드를 거쳐 가는 비용 갱신
			int nextDistance = distance + a[current][i].second;  ////nextDistance= 0+2= 2
			//기존의 최소 비용보다 더 저렴하면 교체
			if(nextDistance < d[next]){                 //// 2 < INF
				d[next]=nextDistance;                   ////d[2] = 2
				pq.push(make_pair(next, -nextDistance));////pq={(2,-2)}
			}  
		}	
	}
}

int main(void){
	for(int i=1;i<=n;i++)
		d[i]=INF;
	
	insert();
	dijkstra(1);
	for(int i=1;i<=n;i++){
		printf("%d ",d[i]);
	}
}


void insert(){
	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));
}