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

최단경로를 찾는 알고리즘 중 하나

특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다

인공위성 GPS 소프트웨어 등에서 가장 많이 사용한다

음의 간선을 포함할 수 없다는 단점이 있으나, 현실세계에서 사용하기에는 매우 적합한 알고리즘

그리디 알고리즘, 또는 DP 알고리즘으로 분류된다

DP 알고리즘으로 분류되는 이유는, 최단 거리를 구하는 과정 중에

하나의 최단거리는 여러개의 최단거리들의 합으로 이루어져있기 때문이다

ex) A->B->C->D 에서 A->D가 최단 경로라면, A->B, B->C 도 최단경로여야 하기 때문

하나의 최단 거리를 구할 때, 그 이전까지 구했던 최단거리 정보를 그대로 사용하기 때문이다

예시

---

다음과 같은 그래프가 주어질 때, 1->3 최단경로 구하기

1. 1에 붙어있는 노드 2,3,4의 최단거리 3,6,7로 산정한다
   • 순차적으로 계산하기 때문에 먼저 붙어있는 노드만 확인 가능
   • 현재 1->3으로 가는 최소 비용은 6이다. 다른 경로는 미확인
2. 3,6,7중 최소 비용인 3을 선택. 다음 노드인 2를 처리하는 경우
   • 1->3의 비용이 6인 반면, 1-2-3의 비용은 4로 더 저렴하므로, 이때의 최소 비용을 갱신한다

이를 정리하면

1. 출발 노드를 설정한다
2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장한다
3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택
4. 해당 노드를 거쳐 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신
5. 위 과정을 3번~4번 반복

구현

---

1. 2차원 배열을 이용한 구현
2. 우선순위 큐를 이용한 구현

1. 2차원 배열을 이용한 구현

• 구현하기 쉽다

• 단계마다 ‘방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택’하기 위해 매 단계마다 1차원 리스트의 모든 원소를 확인(순차탐색)함

• 노드가 10,000개 이상 되면, 느리게 동작한다는 단점이 존재한다

• 정점의 개수가 많은데, 간선은 적은 경우, 비효율적으로 동작함

• 시간 복잡도가 O(V^2) : V는 노드의 개수

#include <iostream>

using namespace std;

int number = 6;
int INF = 21e8;

// 자기 자신은 0, 경로가 없으면 INF로 저장
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 d[6];
bool visited[6];

// 간선 정보 중, 최소 거리 비용을 찾는 함수
// 가장 짧은 거리를 가지는 인덱스를 반환함
int getSmallIndex() {
	int min = INF;
	int index = 0;
	for (int i = 0; i < number; i++) {
		if (d[i] < min && !visited[i]) {
			min = d[i];
			index = i;
		}
	}
	return index;
}

// 다익스트라 함수
// d배열에 최단 경로의 값을 저장한다
void dijkstra(int start) {
	// 1. d 채우기
	for (int i = 0; i < number; i++) {
		d[i] = a[start][i];
	}
	// 2. 시작 지점 방문처리
	visited[start] = true;

	// 3. 가장 최단거리 찾아서 걔부터 방문해보기
	for (int i = 0; i < number; i++) {
		int current = getSmallIndex();
		visited[current] = true;

		for (int j = 0; j < number; j++) {
			if (!visited[j]) {
				if (d[current] + a[current][j] < d[j]) {
					d[j] = d[current] + a[current][j];
				}
			}
		}
	}

}
	

int main(){

	dijkstra(0);

	for (int i = 0; i < number; i++) {
		cout << d[i] << endl;
	}
	
}

2. 우선순위 큐를 이용한 구현 방식

• 우선순위 큐를 이용한다

• 우선순위 큐는 우선순위에 따라 큐가 정렬되고, Heap으로 구현되어있는 자료구조임

• 기본적으로 가장 큰 값이 TOP을 유지하도록 설정 되어있음

• O(E * log V) 의 시간 복잡도를 가진다

• 모든 원소를 선형탐색하는 부분이 우선순위 큐를 사용하여 빠르게 작동함

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int number = 6;
int INF = 21e8;

vector < pair<int, int> > a[7]; // 간선 정보
int d[7]; // 최소 비용

void dijkstra(int start) {
	d[start] = 0; // 시작 노드는 자기 자신과 거리가 0

	priority_queue<pair<int, int>> pq; 
	// 우선순위 큐를 이용해 최소 거리를 가지는 노드를 얻는다
	// pq는 기본적으로 최대값이 앞으로 오른 최대힙

	pq.push({ start, 0 }); // 시작 지점을 우선순위 큐에 넣는다

	while (!pq.empty()) {
		int current = pq.top().first; 
		int distance = -pq.top().second; 
		// -를 붙이는 이유는?
		// 최소값을 얻기 위해 넣을때 음수화하여 저장했기 때문에
		// 최소값이 가장 먼저 나오도록 다시 음수화
		pq.pop();
		// 기존에 저장된 거리보다 긴 경우, 최단 거리가 아니므로 스킵
		if (d[current] < distance) continue;

		// current와 인접한 노드를 하나씩 확인 후 d를 갱신하는 작업
		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({ next, -nextDistance }); // 최소값을 위로 보내기 위해 음수화 하여 저장
			}
		}

	}
}

int main() {
	// 거리 정보를 무한으로 초기화
	for (int i = 1; i <= number; i++) {
		d[i] = INF;
	}

	a[1].push_back({ 2,2 }); // 1->2 cost : 2
	a[1].push_back({ 3,5 }); // 1->3 cost : 5
	a[1].push_back({ 4,1 }); // 1->4 cost : 1

	a[2].push_back({ 1,2 }); 
	a[2].push_back({ 3,3 }); 
	a[2].push_back({ 4,2 }); 

	a[3].push_back({ 1,5 });
	a[3].push_back({ 2,3 });
	a[3].push_back({ 4,3 });
	a[3].push_back({ 5,1 });
	a[3].push_back({ 6,5 });

	a[4].push_back({ 1,1 });
	a[4].push_back({ 2,2 });
	a[4].push_back({ 3,3 });
	a[4].push_back({ 5,1 });

	a[5].push_back({ 3,1 });
	a[5].push_back({ 4,1 });
	a[5].push_back({ 6,2 });

	a[6].push_back({ 3,5 });
	a[6].push_back({ 5,2 });

	dijkstra(1);

	for (int i = 1; i <= number; i++) {
		cout << d[i] << " ";
	}
}

참조 :

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

https://velog.io/@maddie/Algorithm-다익스트라-알고리즘-C