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

📒 다익스트라(Dijkstra)

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

• 다이나믹 프로그래밍(DP)을 활용한 대표적인 최단 경로 탐색 알고리즘
• 다익스트라 알고리즘이 DP인 이유는 최단 거리는 여러 개의 최단 거리로 이루어져 있기 때문이다. (하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다.)
• 흔히 인공위성 GPS 소프트웨어 등에서 많이 사용된다.
  
  

📌 다익스트라 알고리즘의 특성

• 특정한 하나의 정점에서 모든 정점으로 가는 최단 경로를 탐색한다.
• 다만 이때, 음의 간선을 포함할 수 없다. 물론 현실 세계에서는 음의 간선이 존재하지 않기 때문에 다익스트라는 현실 세계에서 사용하기 매우 적합한 알고리즘 중 하나이다. (간선 중 하나라도 가중치가 음수이면 다익스트라 알고리즘을 사용할 수 없다.)
• O((V + E) log V)(V는 정점의 개수, E는 한 정점의 주변 노드)의 시간 복잡도를 갖는다. 이유는 노드마다 미방문 노드 중 출발점으로부터 현재까지 계산된 최단 거리를 가지는 노드를 찾는데, O(V log V)의 시간이 필요하고 노드마다 이웃한 노드의 최단 거리를 갱신할 때 O(E log V)의 시간이 필요하기 때문이다.
  
  

📌 다익스트라 알고리즘의 기본 동작

1. 출발점으로부터의 최단 거리를 저장할 배열 d[v]를 만들고, 출발 노드에는 0, 출발점을 제외한 다를 노드들에는 매우 큰 값 INF(정말 무한이 아닌, 무한으로 간주할 수 있는 값을 의미)를 채워 넣는다.
2. 현재 노드를 나타내는 변수 A에 출발 노드의 번호를 저장한다.
3. A로부터 갈 수 있는 임의의 노드 B에 대해, d[A] + P[A][B](A를 거쳐 B까지 가는 최단 거리)와 d[B](현재까지 알고 있던 B까지의 최단 거리)의 값을 비교한다.
4. 만약 d[A] + P[A][B]의 값이 더 작다면, 즉 더 짧은 경로라면, d[B]의 값을 이 값으로 갱신시킨다.
5. A의 모든 이웃 노드 B에 대해 이 작업을 수행한다.
6. A의 상태를 "방문 완료"로 바꾸고, A는 더 이상 사용하지 않는다.
7. "미방문" 상태인 모든 노드 중, 출발점으로부터의 거리가 제일 짧은 노드 하나를 골라서 그 노드를 A에 저장한다.
8. 도착 노드가 "방문 완료" 상태가 되거나, 혹은 더 이상 미방문 상태의 노드를 선택할 수 없을 때까지, 3~7의 과정을 반복한다.

• 이 작업을 마친 뒤, 도착 노드에 저장된 값이 바로 A로부터의 최단 거리이다. 만약 이 값이 INF라면, 중간에 길이 끊긴 것임을 의미한다.
• 7번 단계에서, 거리가 가장 짧은 노드를 고르는 것은 공짜가 아니다. 모든 노드를 순회해야 하므로 시간 복잡도에 결정적인 영향을 미치게 되는데, 이때 우선순위 큐를 활용한다면 이 비용을 줄일 수 있다. 최단 거리를 갱신할 때 우선순위 큐에도 <위치, 거리>의 쌍을 넣어주고, 거리가 가장 짧은 노드를 우선순위 큐를 이용하여서 고르면 된다.
• 이진 힙을 이용하여 구현한 우선순위 큐의 경우 O(log N) 출력에 O(log N)이므로, 모든 노드 순회 O(N)보다 저렴하다.
• 우선순위 큐 구현에 피보나치 힙을 사용한 경우 삽입은 평균적으로 O(1), 출력에는 O(log N)이 걸려 이론적으로 더 나은 시간 복잡도를 얻을 수 있다. 단, 이진 힙이 훨씬 간단하여 연산에 드는 시간이 빠르기 때문에 간선의 개수가 적은 경우에는 이진 힙을 사용하는 것이 더 나을 수 있다.
  
  

📝 다익스트라 알고리즘 구현

• 구현 방법에는 "방문하지 않은 노드"를 다루는 방식에서 "선형 탐색"을 할 것이냐, "우선순위 큐"를 사용할 것이냐로 나눌 수 있다.
  
  

선형 탐색

// C++
#include <iostream>

const int INF = ; // 무한대를 의미하는 수를 표현
const int N = ; // 정점의 개수

int graph[N][N] = ; // 그래프 초기화

bool visited[N]; // 방문 여부 저장
int distance[N]; // 최단 거리

// 방문하지 않은 노드 중, 거리가 최솟값인 노드의 인덱스 반환
int getMinDistanceIndex()
{
	int min_dist = INF;
	int min_idx = -1;

	// 선형 탐색
	for (int i = 0; i < N; ++i)
	{
		if (distance[i] < min_dist && !visited[i])
		{
			min_dist = distance[i];
			min_idx = i;
		}
	}

	return min_idx;
}

// 다익스트라 함수
void dijkstra(int start)
{
	for (int i = 0; i < N; ++i)
	{
		distance[i] = graph[start][i];
	}

	visited[start] = true;

	for (int i = 0; i < N - 2; i++)
	{
		int current = getMinDistanceIndex();
		visited[current] = true;

		for (int j = 0; j < N; ++j)
		{
			if (!visited[j])
			{
				if (distance[current] + graph[current][j] < distance[j])
				{
					distance[j] = distance[current] + graph[current][j];
				}
			}
		}
	}
}

• 위 코드는 가장 쉽게 다익스트라 알고리즘을 구현하는 방법이다.
• 하지만 이 방법으로 탐색하는 경우 시간 복잡도가 O(N^2)이다.
• 특히, 정점의 개수는 많은데 간선의 개수가 적을 때 치명적으로 비효율적일 수 있다.
  
  

우선순위 큐

// C++
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

const int INF = ; // 무한대를 의미하는 수를 표현
const int N = ; // 정점의 개수

vector<pair<int, int>> graph[N + 1]; // 간선 정보
int d[N + 1]; // 최소 비용

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 < graph[current].size(); ++i)
		{
			// 해당 노드의 인접 노드
			int next = graph[current][i].first;
			// 해당 노드를 거쳐서 인접 노드로 가는 비용
			int nextDistance = distance + graph[current][i].second;
			// 기존의 최소 비용보다 더 작다면 교체
			if (nextDistance < d[next])
			{
				d[next] = nextDistance;
				// 최솟값이 우선순위가 되도록 음수 부호를 붙인다.
				pq.push(make_pair(next, -nextDistance));
			}
		}
	}
}

• 위 코드는 힙 구조를 활용하여 시간 복잡도를 O(N log N)으로 구현하는 방법이다.
• 이 경우에는 정점에 비해 간선의 개수가 적어도 안정적으로 처리가 가능하다.