다익스트라 알고리즘 [C++]

도저히 Python으로는 다익스트라 알고리즘의 원리가 이해가지 않아 C++로 다시 개념을 정리하였습니다.

 

우선순위 큐를 사용하지 않는 코드

그래프 예시

#include <stdio.h>
int number = 6;
int INF = 100000000;

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];
	}	// 그래프에서 선택한 노드의 거리를 옮겨온다.

	v[start] = true; // 시작노드는 방문했으므로 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(void) {
	dijkstra(0);
	for (int i = 0; i < number; i++) {
		printf("%d ", d[i]);
	}
}

 

코드는 아래 블로그에서 따왔습니다.

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

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

 

간략하게 코드의 메커니즘을 따라가보면

방문 여부를 확인하는 변수 v와, 각 노드가 연결하는 간선의 가중치 (거리)를 저장하는 변수 d 가 있고, 그래프를 표현하고 있는 2차원 배열 a가 존재합니다.

int number = 6;
int INF = 100000000;

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];	// 거리

 

 

함수 getSmallIndex는 현재 방문하고 있는 노드가 가르키고 있는 가장 짧은 노드를 반환합니다.

전역변수이므로 따로 파라미터를 받을 필요는 없습니다.

해당 함수의 코드부는 어렵지 않으므로 간략하게 한줄로 설명하겠습니다.

코드 내에서 가장 크게 존재하는 변수 INF로 min 값을 설정 한 뒤, 배열을 돌면서 min보다 작은 값을 대입해가는 선형 구조로 되어있습니다.

 

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;
}

 

마지막으로 다익스트라 핵심 코드를 보면, 파라미터 값으로 start 노드를 받고 있습니다.

해당 노드에서 각 노드까지 가장 짧은 거리를 얻기 위함이라고 생각하면 되는데 매커니즘은 아래와 같습니다.

 

1. 시작 노드로부터 연결 된 간선의 배열을 받아 배열 d에 복사한다.
2. 시작 노드의 방문여부를 True로 설정한다.
3. number -2 한 이유는 단순히 start 노드는 check 하였고, 번호가 0번부터 시작이므로 -2 한것이다.
4. 시작 노드 이외 순차 방문하면서, 값을 비교하고, 새로운 길 즉 다른 노드를 통해 가는 길이 이전 방법보다 짧다면 가장 짧은 거리를 갱신한다.

아래는 반복문을 돌면서 가장 짧은 노드가 어떤식으로 변했는지 나타내는 결과 창입니다.

직접 손으로 해보면서 검증해보니 훨씬 이해가 더 잘갔습니다.

 

 

우선순위 큐 사용

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

using namespace std;

int number = 6;
int INF = 100000000;

vector <pair<int, int> >a[7];	// 노드와, 연결된 거리를 저장할 pair vector
int d[7];	// 선택된 노드로부터 연결된 노드까지의 거리를 저장할 배열

void dijkstra(int start) {
	d[start] = 0;	// 선택된 노드로 가는 거리는 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;	// 음수를 넣음으로서 뺄 때 가장 작은 수부터 빼도록 함. (grater<int>)사용 해도 됨,
		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]);
}

같은 그래프를 이용하였고, 선택한 노드에서 가장 짧은 거리를 찾기 위해 최소 힙을 사용한다.

우선순위 큐를 사용한다면 가장 짧은 노드를 선형으로 탐색할 필요가 없기 때문에 훨씬 시간복잡도가 적어진다.