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

다익스트라 알고리즘 : 그래프에서 꼭짓점 간의 최단 경로를 찾을 수 있는 알고리즘이다. 

 

한 꼭짓점을 고정하고, 그래프의 다른 꼭짓점까지 최단 경로 트리를 만들며 이동하는 방식으로 구현한다. 

다이나믹 프로그래밍의 한 종류인데, 최단거리를 구하는 매 과정에서 이전 단계에서 구한 최단거리를 사용하기 때문이다. 

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

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

 

1) 이차원 배열의 형태로 n행 m열의 값을 n번에서 m번 노드로 가는 비용을 저장한다. 

2) 시작 노드(방문 처리)에서 인접 노드를 탐색, 이동하는 데 드는 비용을 배열에 저장한다.  

3) 가장 비용이 적은 노드를 탐색하고, 그 노드로 이동하여 새롭게 최소 비용 배열을 갱신해준다. 

4) 이동한 노드에 대해 방문처리하고, 방문하지 않은 노드 중 최소 비용인 노드를 찾아 이동해준다. 

 

#include <iostream>
using namespace std;

int number = 6;
int INF = 10000000; // 무한

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 visit[6];
int d[6];

// 최소 거리의 정점을 반환
int getSmallIndex() {
	int min = INF;
	int index = 0;
	for (int i = 0; i < number; i++) {
		if (d[i] < min && !visit[i]) { // 방문하지 않은 노드
			min = d[i];
			index = i;
		}
	}
	return index; // 최소 인덱스 반환
}

void dijkstra(int start) {
	for (int i = 0; i < number; i++) {
		d[i] = a[start][i]; // 시작 노드와 인접 노드의 거리
	}
	visit[start] = true;
	for (int i = 0; i < number - 2; i++) {
		int current = getSmallIndex(); // 현재 배열에서 가장 작은 노드의 번호
		visit[current] = true; // 방문 처리
		for (int j = 0; j < 6; j++) {
			if (!visit[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++) {
		printf("%d ", d[i]);
	}
}

 

위 알고리즘은 선형 탐색으로 구현되었으며  O(n^2)의 시간 복잡도를 가진다. 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int number = 6;
int INF = 10000000; // 무한대

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 current = pq.top().first; 
		int distance = -pq.top().second; // 짧은 거리가 먼저 오도록 음수화
		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));
			}
		}
	}
}

힙 구조를 사용해서 선택한 노드(current)에 있는 인접 노드들의 정보를 순회하며

최소 거리에 위치한 노드를 찾아 이동하며 최소 비용 배열에 현재 거리를 대입한다. 

이렇게 매 순회마다 최소 거리를 찾아 d배열과 방문한 노드임을 힙 구조에 넣음으로써 처리한다. 

 

이 알고리즘은 for문 안에서 힙 기반 데이터 삽입을 구현하므로 O(N * logN)의 시간 복잡도를 가진다.