다익스트라(Dijkstra) 알고리즘과 최단경로 역추적

다익스트라 알고리즘을 활용하여 최단경로를 구할 때, 최단경로의 길이 뿐만 아니라 정확한 경로를 역추적 해야하는 필요성을 느낄 때가 있다.

기본적인 다익스트라 알고리즘은 다음과 같은 과정으로 이루어진다.

 

1. dist[i](시작정점 S에서 i로 가는 최단경로 값) 배열을 INF로 초기화한다.

2. 시작정점인 dist[S]를 0으로 초기화하고, 정점과 그 정점까지의 거리 {거리, 정점}을 우선순위 큐에 넣어준다.

3. 거리가 작은 순으로 우선순위가 구성된 우선순위 큐에서 값을 하나씩 꺼내며 기존 dist[vertex]보다 값이 작거나 같은 경우 작업을 수행한다.

4. 현재 정점 now와 인접한 임의의 정점을 next라고 할 때, 현재 정점에 연결된 간선을 모두 조사하며 dist[next] 배열을 더 작은 값으로 변경할 수 있는 경우 값을 변경하고 우선순위 큐에 {dist[next], next}를 저장한다.

5. 우선순위 큐가 빌 때까지 이를 반복한다.

 

long long dist[size];
priority_queue <pair<long long, int>, vector<pair<long long, int>>, cmp> pq;

void Dijkstra(int S) {
	for (int i = 1; i <= size; i++) dist[i] = INF; // 1번
	pq.push({ 0, S });
	dist[S] = 0; // 2번
	while (pq.size()) {
		int now = pq.top().second;
		long long val = pq.top().first;
		pq.pop();
		if (dist[now] < val) continue; // 3번
		for (int i = 0; i < graph[now].size(); i++) {
			int next = graph[now][i].second;
			long long new_val = val + graph[now][i].first;
			if (dist[next] > new_val) { // 4번
				dist[next] = new_val;
				pq.push({ new_val, next });
			}
		}
	}
}

이 과정에서 path[vertex]이라는 vector을 선언하여 최단경로를 기록할 수 있다.

path[vertex]에는 최단경로로 vertex에 도달하기 위해 바로 직전에 방문하였던 정점을 기록한다.

 

위에서 설명한 다익스트라 알고리즘 4번에서 dist[next] 배열에 기존보다 더 작은 값을 기록할 수 있는 경우, 이는 현재까지 발견한 경로 중 가장 짧은 경로이므로, path[next] 배열을 비우고, path[next] 배열에 now 정점을 추가한다.

 

path[next] 배열을 비우는 이유는 최단경로의 특성 때문이다. 어떠한 정점을 최단경로로 방문하기 위해서는 그 정점을 방문하기 위해 거쳐야 하는 모든 정점을 최단경로로 방문하여야 한다. 따라서, 그 이전에 저장되었던 무의미한 경로를 지워주는 것이다.

 

다만, 이 과정에서 now 정점을 통해 next 정점을 방문하는 값과 dist[next] 배열이 같은 값이라면, 이는 서로 다른 최단경로 중 하나이므로 path[next] 배열을 비우지 않고 now 정점을 추가하여 준다.

long long dist[size];
vector <int> path[size];
priority_queue <pair<long long, int>, vector<pair<long long, int>>, cmp> pq;

void Dijkstra(int S) {
	for (int i = 1; i <= size; i++) dist[i] = INF;	
	pq.push({ 0, S });
	dist[S] = 0;
	while (pq.size()) {
		int now = pq.top().second;
		long long val = pq.top().first;
		pq.pop();
		if (dist[now] < val) continue;
		for (int i = 0; i < graph[now].size(); i++) {
			int next = graph[now][i].second;
			long long new_val = val + graph[now][i].first;
			if (dist[next] > new_val) {
				dist[next] = new_val;
				path[next].clear(); // 기존의 경로는 무의미
				path[next].push_back(now); // 새 경로를 저장
				pq.push({ new_val, next });
			}
			else if (dist[next] == new_val) path[next].push_back(now); // dist[next]가 새로운 값과 같은 경우에도 유효한 경로
		}
	}
}