다익스트라 알고리즘

개요

다익스트라 알고리즘은 최단 경로를 구하는 알고리즘 중 하나이다. 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 이 때 음의 간선은 음의 값을 가질 수 없다는 특징이 있다.

동작

구체적인 동작 과정은 다음과 같습니다

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

출발지를 A로 설정했다고 가정하자.
A와 A사이의 거리는 0이므로 0값을 가진다. 즉 d[A] = 0 이다.
A와 직접 간선으로 연결된 점은 B, C, D 총 3개이다.
이 3개의 점은 각각 A사이의 거리인 10, 30, 15로 설정해준다.
나머지 E와 F의 경우 A와 연결되어 있지만, 직접적으로 연결되어 있지 않기에, 정확한 거리를 알 수 없으므로 무한대인 Infinity 값으로 설정해준다.

방문할 노드의 집합인 Q중 가장 비용이 적은 노드인 B를 선택한다.
B의 이웃노드는 E뿐이므로, d[E]의 값을 10 + 20 = 30으로 설정해준다.

방문할 노드의 집합 Q중 가장 비용이 적은 노드는 D이다.
D의 이웃 노드들의 거리를 잰 후 작은 값으로 업데이트해주면 된다.
D를 방문하여 C를 방문하는 경우가 이전값인 30보다 더 작으므로 d[C]의 값을 15 + 5 = 20 으로 설정해준다.

F의 경우는 Infinite에서 D를 통하여 경로를 설정할 수 있으므로, 15 + 20 = 35로 설정해준다.

다음으로 Q중 가장 비용이 적은 노드는 F이다.
F를 방문하기 위한 여러 경로들을 비교해보면, D를 통해 F값에 도달하는 것 보다, A -> D -> C -> F 로 방문하는 것이 비용이 더 적기에 25로 업데이트해준다.

이렇게 반복하여 Q가 공집합이 되었다면, 우리는 원하는 결과를 얻은 것이다.

코드

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

using namespace std;

int number = 6;
int INF = 100000000;

int a[6][6] = {
	{0, 10, 30, 15, INF, INF},
	{10, 0, INF, INF, 20, INF},
	{30, INF, 0, 5, INF, 5},
	{15, INF, 5, 0, INF, 20},
	{0, 20, INF, INF, 0, 20},
	{INF, INF, 5, 20, 20, 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];
	}
	v[start] = true;
	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() {
	dijkstra(0);
	for (int i = 0; i < number; i++) {
		cout << d[i] << "  ";
	}

	return 0;
}