[C++] 다익스트라(Dijkstra)

 

 

 

다익스트라(Dijkstra) 알고리즘은 그래프에서 특정 지점에서 모든 노드를 지나는 최단 거리를 구할 때 사용하는 알고리즘이다. 이때 그래프가 다음 특성을 가질 때 사용 가능하다.

• 모든 Edge의 비용이 양수여야 한다.

다익스트라의 시간 복잡도는 O(E * log V)이다.

 

 

 

 

 

다익스트라 자료구조

 

먼저, 그래프를 표현하기 위해서 인접 리스트 자료구조를 사용한다.

인접 리스트의 인덱스는 Start 노드이며, 각 인덱스에 해당하는 요소는 (End 노드, 가중치)이다.

 

만약 양방향 그래프의 경우 이방향에 대해 저장해줘야 한다.

 

 

 

 

추가로 최단 거리 배열이 필요하다. 이것은 다익스트라 원리를 구현하기 위해 필요한 자료구조이다.

처음에는 무한대에 가까운 Dummy 값으로 초기화해준다. (시작 노드는 0으로 초기화)

 

또한, 반복된 방문을 방지하기 위해 방문 여부 배열이 필요하다.

혹은 우선순위 큐를 이용하면 더 빠르게 수행할 수 있다.

코드에서 우선순위 큐를 활용하여 구현해보겠다.

 

 

 

 

 

다익스트라 원리

 

다익스트라의 원리는 다음을 따른다.

1. 최단 거리 배열에서 값이 가장 작은 노드를 선택한다.
2. 해당 노드와 연결된 모든 Edge에 대해 최단 거리 배열을 업데이트한다. 이때, 업데이트 방식은 ⓐ Edge 노드의 최단 거리와 ⓑ (현재 노드의 최단 거리 + Edge 가중치) 중에서 작은 값으로 업데이트한다.
3. 모든 노드를 방문할 때까지 이 과정을 반복한다.

이 원리로 완성된 최단 거리 배열의 의미는 시작 노드에서 i 번째 노드까지의 최단 거리를 의미한다.

 

 

 

 

 

다익스트라 코드 (리스트)

vector<int> dijkstra(const vector<vector<pair<int, int>>> graph, int node_num, int start)
{
	vector<bool> isVisited(node_num + 1, false);
	vector<int> result(node_num + 1, DUMMY);
	int now = start;

	result[now] = 0;
	for (int i = 0; i < node_num; i++)
	{
		isVisited[now] = true;
		for (auto pair : graph[now])
			if (result[now] + pair.second < result[pair.first])
				result[pair.first] = result[now] + pair.second;

		now = 0;
		for (int j = 1; j <= node_num; j++)
		{
			if (isVisited[j]) continue;
			if (result[j] < result[now])
				now = j;
		}
	}
	return result;
}

 

 

 

 

 

다익스트라 코드 (우선순위 큐)

vector<int> dijkstra(const vector<vector<pair<int, int>>> graph, int node_num, int start)
{
	vector<int> result(node_num + 1, DUMMY);
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	int now = start;

	pq.push({ 0, now });
	result[now] = 0;
	while (!pq.empty())
	{
		int weight = pq.top().first;
		now = pq.top().second;
		pq.pop();

		if (weight > result[now])
			continue;

		for (auto pair : graph[now])
		{
			int next_weight = pair.first;
			int next = pair.second;
			if (result[now] + next_weight < result[next])
			{
				result[next] = result[now] + next_weight;
				pq.push({ result[next], next });
			}
		}
	}

	return result;
}