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

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

다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다(이때 음의 간선은 포함될 수 없다). 현실세계에서는 음의 간선이 존재하지 않기 때문에 다익스트라 알고리즘은 현실 세계에서 적용하기에 매우 적합한 알고리즘이라고 할 수 있다.

 

다익스트라 알고리즘이 다이나믹 프로그래밍 문제인 이유는 '최단 거리는 여러 개의 최단 거리로 이루어져있기 때문이다.' --> 현재까지 알고 있던 최단 경로를 계속해서 갱신한다!

 

이번 게시물에서의 그래프 예시는 위와 같이 정했다. 먼저, 배열을 사용해서 다익스트라 알고리즘을 완성해보자.

 

#include <iostream>

using namespace std;

int number = 6;
int INF = 100000;
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 v[6];

int getIndex() {
	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) {
	v[start] = true;
	for (int i = 0; i < number; i++) {
		d[i] = a[start][i];
	}
	for (int i = 0; i < number - 2; i++) {
		int next = getIndex();
		v[next] = true;
		for (int j = 0; j < number; j++) {
			if (d[j] > a[next][j] + d[next]) {
				d[j] = a[next][j] + d[next];
			}
		}
	}

}

int main() {
	dijkstra(0);
	for (int i = 0; i < number; i++) {
		printf("%d ", d[i]);
	}

	return 0;
}

 

위와 같이 구현할 수 있으나 선형 탐색으로 구현하였기에 시간 복잡도가 O(n^2)이 된다. 하지만 우리는 힙 구조를 활용하여 시간 복잡도를 줄일 수 있다.

 

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

using namespace std;

int number = 6;
int INF = 100000;

vector <pair<int, int>> a[7];
int d[7];

void dijkstra(int start) {
	priority_queue<pair<int, int>> pq;
	d[start] = 0;
	pq.push(make_pair(0, start));

	while (!pq.empty()) {
		int current = pq.top().second; // priority_queue는 first부터 비교하기 때문에 vector a[]와 인덱스 순서가 다르다.
		int distance = -pq.top().first; // priority_queue는 최대 힙 구조이기 때문에 꺼내고 집어넣을때 음수(-)처리를 해준다.
		pq.pop();

		for (int i = 0; i < a[current].size(); i++) { // 현재 노드에서 인접한 노드에 대해 for문을 돌린다.
			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() {
	int edge = 0;
	scanf("%d", &edge);

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

	for (int i = 0; i < edge; i++) {
		int from, to, val = 0;
		scanf("%d %d %d", &from, &to, &val);
		a[from].push_back(make_pair(to, val));
	}

	dijkstra(1);

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

	return 0;
}

위 소스코드는 vector를 사용하여 시간 복잡도를 O((V+E)logV)까지 줄일 수 있다(V는 정점의 개수, E는 한 정점의 주변 노드의 개수).