다익스트라 알고리즘

#

dist배열을 INT_MAX로 초기화한다

우선순위 큐를 하나 선언한다.

우선순위 큐에 시작하는 노드와 거리(0)쌍을 push한다.

우선순위 큐가 빌때까지 다음을 반복한다.

##

우선순위 큐에서 거리가 최소인 노드(now)와 거리(cost)를 뽑는다.

기존의 now까지 가는 거리보다 방금 큐에서 뽑은 거리가 더 멀면 무시하고 컨티뉴(dist[now] < cost : continue)

now와 연결된 모든 노드에 대해 다음을 반복한다.

###

(now까지의 거리 + now에서 다음노드까지의 거리)보다 dist[다음노드]가 더 짧다면 갱신해줘야 하는 노드이다.

따라서 dist[다음노드]를 갱신해주고, 우선순위 큐에 (dist[다음노드], 다음노드)를 push해준다.

###

##

#

주의할점은 두가지

1. 우선순위 큐의 기본 정렬은 내림차순이기 때문에 greater를 선언에 넣어주어서 오름차순으로 변경해준다.

2. 우선순위 큐에 pair를 넣어주면 pair.second보다 pair.first를 기준으로 정렬하기 때문에 큐에 넣는 pair는 (거리, 노드)의 형태로 넣어야 한다.

3. 우선순위 큐에 들어가는 것은 (거리, 노드)이다. 즉, edge가 큐에 들어간다.

int N, E;
int dist[20002];
vector<pair<int, int>> adj[20002];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

void dijkstra(int startNode) {

	for (int i = 1; i <= N; i++) {
		dist[i] = INT_MAX_;
	}
	dist[startNode] = 0;

	pq.push(make_pair(0, startNode));
	while (!pq.empty()) {
		int cost = pq.top().first;
		int now = pq.top().second;
		pq.pop();
		if (dist[now] < cost) continue;
		for (pair<int, int> next : adj[now]) {
			if (dist[next.second] > next.first + cost) {
				pq.push(make_pair(next.first + cost, next.second));
				dist[next.second] = next.first + cost;
			}
		}
	}

	return;
}