다익스트라(dijkstra) 최단 경로

풀이

다익스트라 알고리즘은 탐욕법과 동적 계획법을 같이 사용합니다. i 노드까지 최단 경로를 구하는 점화식 dist[i]가 등장하며 이를 구하기 위해 매번 최선의 선택(최소 가중치)을 수행합니다. 기본적인 흐름은 다음과 같습니다. 시작 노드를 방문하면서 시작합니다.

 

1. 방문한 노드에서 방문할 수 있는 다른 노드까지의 거리를 구합니다. 그 거리가 기존 값보다 짧으면 새로 갱신합니다.

 

2. 거리가 새로 갱신된 노드만 우선순위 큐에 넣습니다. 중복 방문을 없애기 위해서입니다. 이 외에도 중복 방문을 막기 위한 코드가 한 줄 더 있습니다.

 

3. 이 중에서 간선의 가중치가 최소인 노드를 방문합니다(우선순위 큐를 이용하면 최소 가중치를 쉽게 구할 수 있음).

 

4. 1번으로 갑니다.

 

코드

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

int N = 10, E = 19;
const int INF = 100000000;

vector<vector<int>> nodes(N, vector<int>(N));
vector<int> dist(N, INF);
using PairInt = pair<int, int>;

void dijkstra(int start)
{
	// 방문할 노드를 담아두는 곳(최소 가중치인 곳)
	// first는 방문한 노드까지의 최소 가중치, second는 방문한 노드
	priority_queue<PairInt, vector<PairInt>, greater<PairInt>> pq; 
	// 시작 노드의 가중치는 0
	pq.push({ 0, start });
	dist[start] = 0;
	while (!pq.empty())
	{
		auto [length, current] = pq.top(); pq.pop();
		if (dist[current] < length) continue;

		for (int i = 0; i < nodes[current].size(); ++i)
		{
			if (0 == nodes[current][i]) continue;

			auto sum = dist[current] + nodes[current][i];
			if (sum < dist[i])
			{
				dist[i] = sum;
				pq.push({ dist[i], i });
			}
		}
	}
}

int main()
{
	nodes[0][1] = 10;
	nodes[0][2] = 17;
	nodes[0][3] = 30;
	nodes[0][4] = 25;
	nodes[0][5] = 23;
	nodes[1][2] = 20;
	nodes[2][4] = 17;
	nodes[3][1] = 19;
	nodes[3][6] = 24;
	nodes[4][7] = 25;
	nodes[4][8] = 39;
	nodes[5][3] = 16;
	nodes[5][4] = 28;
	nodes[5][6] = 18;
	nodes[6][9] = 20;
	nodes[7][8] = 29;
	nodes[8][5] = 20;
	nodes[8][9] = 28;
	nodes[9][7] = 40;	

	dijkstra(0);

	cout << dist[9] << endl;
}

방문을 하려고 우선 순위 큐에 삽입을 했는데 dist[i]를 갱신하는 과정에서 큐에 삽입한 값보다 dist[i]가 작아졌을 경우에는 방문하지 않습니다. 왜냐하면 dist[i]를 계산하면서 차후에 방문하기 위해 동일 {가중치, 노드}가 큐에 들어갔기 때문입니다. 그리고 이 코드는 배열의 개수를 고정해버렸기 때문에 문제에 그대로 적용하면 메모리 초과 오류가 날 수 있습니다. 그 경우 벡터를 이용해서 간선이 부여되는 만큼만 노드를 추가하면 됩니다.