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

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

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

하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 사용하는 특징을 가지며, 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 구할 수 있다. 

 

작동 과정

0. 모든 노드의 최소비용을 INF로 초기한다.

1. 시작 노드를 설정하고, 해당 노드의 비용을 0으로 해준다.

2. 시작 노드를 기준으로 각 노드의 최소 비용을 저장한다. 

3. 방문하지 않은 노드 중에 가장 비용이 적은 노드를 선택한다. 이 때, 비용이 같은 노드가 여러개 있다면 맨 앞에 있는 노드를 선택한다.

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

5. 모든 노드를 방문할 때까지 3번과 4번 과정을 반복한다.

 

우선순위 큐를 이용한 소스코드

#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 distance = -pq.top().first;
		int current = pq.top().second; //pq의 최상단 노드에 있는 첫번째값을 현재방문


		pq.pop(); //queue에서 하나를 꺼냄
		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(-nextdistance, next)); //음수화
			}
		}
	}
}

int main() {
	//기본적으로 연결되지 않은 경우는 무한
	for (int i = 1; i <= number; i++){
		d[i] = INF;
	}

	a[1].push_back(make_pair(2, 2)); //1번 노드에서 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(2, 3));
	a[3].push_back(make_pair(4, 3));
	a[3].push_back(make_pair(5, 1));
	a[3].push_back(make_pair(1, 5));
	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]);
	}

}

References

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