[C++] 다익스트라(Dijkstra) 알고리즘 개념

다익스트라 알고리즘이란?

다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘입니다.

대표적으로 인공위성 GPS 소프트웨어 등에서 많이 사용됩니다. 다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줍니다.(음의 간선은 포함 불가)

기본적으로 다익스트라 알고리즘은 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다는 특징이 있습니다.

 

예시코드

void Dijkstra(int s, int e) {
	priority_queue<pair<int, int>>pq; // {index, distance}
	for (int i = 1; i <= N; i++)
		d[i] = INF;
	pq.push({ s, 0 });
	while (!pq.empty()) {
		int cur = pq.top().first;
		int distance = -pq.top().second;//거리가 작은 순으로 정렬하기 위해 음수화해줌
		pq.pop();

		if (d[cur] < distance)continue;
		for (int i = 0; i < city[cur].size(); i++) {
			//다이나믹 프로그래밍을 활용한 다익스트라 알고리즘
			int next = city[cur][i].first;
			int nextDistance = distance + city[cur][i].second;
			if (nextDistance < d[next]) {
				d[next] = nextDistance;
				pq.push({ next,-nextDistance });
			}
		}
	}
	cout << d[e];
}

작동 과정

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

*위에 예시로 구현된 다익스트라 알고리즘은 인접 리스트 방식을 활용하여 O(N * logN)의 시간복잡도를 갖습니다.