[알고리즘] 다익스트라(Dijkstra) 알고리즘이란?

 

다익스트라(Dijkstra) 알고리즘은 재귀호출 없이 다이나믹 프로그래밍을 이용하여 최단거리(최소비용)을 구하는 알고리즘이다.

특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 계산한다. DP(Dynamic Programming)으로 분류되는 이유는 하나의 최단 거리를 구할 때, 그 이전까지 구했던 최단 거리 정보를 그대로 사용하기 때문이다.

단, 음의 간선(가중치)이 있는 경우에는 사용할 수 없는 알고리즘이다.

 

다익스트라 알고리즘의 원리

다음과 같은 규칙을 반복하면 최소 비용을 구할 수 있다.

1. 가장 저렴하게 갈 수 있는 곳을 경유지로 선택한다.
2. 선택된 경유지를 거쳐 다른 곳으로 이동할 때, 더 저렴한 지 확인한다.
3. 더 저렴하다면, 최소비용 전광판 result에 갱신한다.

 

다익스트라 알고리즘의 상세 과정

초기 상태

전광판(result)에서 출발지는 0으로, 길이 없는 경우는 무한(999999)로 세팅한다.

 

과정 1

경유지로 한번 선택 되었다면, via 배열에 1로 세팅해준다.

A는 출발지로, 제외시키기 위해 via[0] = 1로 초기 세팅한다.

먼저 via가 0인 곳 중에서 가장 저렴한 곳을 선택한다. 여기서는 D가 선택된다.

 

과정 2

A에서 출발하여 D까지 가는 최소거리는 20이다.

이때 다음을 비교하여 더 저렴한 비용을 전광판에 기록한다.

 

D를 경유하여 다른 지역(A, B, C)로 가는 비용

vs

전광판(result)에 써있는 다른 지역(A, B, C)으로 가는 비용

 

 

과정 3

D를 들렀다가 B로 가는 비용 : 20 + 10 = 30이고,

전광판(result)에 써있는 B까지 가는 비용은 50이므로, 전광판에서 B의 값을 30으로 수정한다.

 

과정 4

D를 들렀다가 C로 가는 비용 : 20 + 25 = 45이고,

전광판(result)에 써있는 C까지 가는 비용은 999999이므로, 전광판을 수정한다.

 

과정 5

이제 경유지 D의 역할은 끝났으므로, via에서 D를 1로 세팅하고, 새로운 경유지를 찾는다.

via가 0인 곳 중 가장 저렴한(30) 곳인 B를 선택한다.

 

과정 6

A에서 B를 들렀다가 C로 가는 비용 : 30 + 5 = 35이고,

전광판(result)에 써있는 C까지 가는 비용은 45이므로, 전광판을 수정한다.

 

과정 7

이제 경유지 B의 역할은 끝났으므로(B에서 D로 가는 방법은 없음), via에서 B를 1로 세팅하고 경유지를 찾는다.

 

via가 0인 곳이 C로 한 곳 남았지만, A->C로 가는 방법이 없으므로 최종적으로 다익스트라 알고리즘이 마무리된다.

 

💻전체적인 소스코드는 다음과 같다.

#include <iostream>
using namespace std;
const int NOT = 999999; 

//그래프 하드코딩
//간선이 없는 경우 NOT 세팅
int map[4][4] = {
	0, 50, NOT, 20,
	NOT, 0, 5, NOT,
	NOT, NOT, 0, NOT,
	NOT, 10, 25, NOT
};

int result[4] = { 0, 50, NOT, 20 };
int via[4] = { 1, 0, 0, 0 }; //출발지인 A는 1로 세팅

//전광판(result)에서 가장 저렴한 경유지 찾기
int getMin()
{
	int Min = 21e8;
	int minIndex;
	for (int i =0;i<4;i++)
		if (via[i] == 0 && result[i] < Min)
		{
			Min = result[i];
			minIndex = i;
		}
	return minIndex;
}

int main()
{
	int min, minIndex;
	for (int i = 0; i < 3; i++)
	{
		//via가 0인 곳 중 가장 저렴한 경유지
		minIndex = getMin();

		for (int j = 0; j < 4; j++)
		{
			//a = 경유지 까지 비용 + 경유지에서 도착지까지 비용
			int a = result[minIndex] + map[minIndex][j];
			//b = A(출발지)에서 도착지까지 비용
			int b = result[j];
			//경유하는게 더 저렴한 경우
			if (a < b) result[j] = a;
		}
		//탐색을 종료한 경유지는 via를 1로 체크
		via[minIndex] = 1;
	}
	for (int i = 0; i < 4; i++)
		cout << (char)(i+'A') << " : " << result[i] << endl;
	return 0;
}

출력 결과

A : 0
B : 30
C : 35
D : 20

 

 

다익스트라 알고리즘의 경우, 가장 저렴한 경유지를 찾을 때 minHeap을 사용하면 성능을 더 높일 수 있다.

minHeap을 사용하여 구현하는 방법은 다음👇에서 확인할 수 있다.

[알고리즘] 다익스트라(dijkstra) 알고리즘 : MinHeap 사용

[알고리즘] 다익스트라(Dijkstra) 알고리즘 : MinHeap 사용