[C++] Dijkstra 역추적하는 방법

이번 글에서는 Dijkstra 알고리즘을 역추적하는 방법에 대해서 설명해보고자 합니다.

 

Dijkstra 관련 문제들을 풀다보면 가끔씩 최단 경로를 출력하라는 문제들을 볼 수 있습니다.

이럴 때에는 도착 노드부터 시작 노드까지 역으로 추적하는 방법으로도 최단 경로를 찾을 수 있습니다.

 

그러면 어떻게 역추적을 하면 될까요? 일단 최단 경로의 특성에 대해서 알아보도록 합시다.

노드 A, B가 각각 시작 노드와 도착 노드라 합시다.

그리고 A와 B간의 최단 경로에 K라는 노드가 속할 수 있다고 합시다.

그렇다면 다음과 같은 식이 성립합니다. 

 

A -> B의 최단 거리 = (A -> K의 최단 거리) + (K -> B의 최단 거리)

 

이러한 식은 A -> B의 최단 경로에 속하는 모든 노드들에 대해서 적용할 수 있습니다.

그렇다면 A -> K의 최단 거리 = (A -> B의 최단거리) - (K -> B의 최단거리)  이러한 식도 말이 되겠지요?

이러한 특징으로 역추적이 가능합니다.

 

최단 경로 중에서 B 노드 바로 전에 들리는 노드를 B'라고 합시다.

그렇다면 B' -> B의 최단거리 = B' -> B로 가는 간선의 거리가 됩니다.

그렇다면 A -> B'의 최단거리 = (A -> B의 최단거리) - (B' -> B 간선의 거리) 이게 만족하게 됩니다.

그러면 이제 B' 노드를 들리기 직전에 들리는 B''라는 노드는 A -> B'' 의 최단거리 = (A -> B'의 최단거리) - (B'' -> B' 간선의 거리)를 만족합니다.

 

그래서 역추적을 하는 방법은 다음과 같습니다.

 

1. 도착 노드 B부터 보기 시작한다.

 

2. 현재 보고 있는 노드를 curr이라고 하자, 그리고 curr를 도착점으로 하는 간선들의 시작점을 bef라고 하자.

그렇다면 A -> bef의 최단거리 = (A -> curr의 최단거리) - (bef -> curr의 간선의 거리)를 만족하는 아무 노드 bef를 찾는다.

 

3. 그렇다면 최단경로 상에서 bef가 curr 전에 들리는 노드이므로 curr를 bef로 업데이트 한다.

 

4. curr가 시작 노드인 A가 되면 그만둔다.

 

이러면서 curr를 계속 기록을 해두면 됩니다. curr == A 가 되는 순간에는 이제 기록해둔 것을 거꾸로 뒤집으면 최단경로가 나옵니다. C++ 코드로는 아래와 같이 구현하면 됩니다.

 

// 전에 이미 선언되어 있는 것들
// #define ll long long
// vector<ll> dist(N+1) : 시작점으로 각 노드까지의 최단거리를 담은 array. Dijkstra를 돌린 결과.
// vector<vector<pair<ll,ll>>> E2(N+1) : E2[n] = n이 도착점인 간선들의 정보, 각 간선들은 {간선의 시작점, 간선의 거리}로 표현됨 

vector<ll> path; // 최단경로
ll curr = B;
while(curr != A){
	path.push_back(curr);
    for(auto itr : E2[curr]){ // 역간선들을 보았을 때에
    	ll bef, cost;
        tie(bef, cost) = itr;
        if(dist[bef] = dist[curr] - cost){ // A -> bef 최단거리 = A -> curr 최단거리 - bef -> cost 간선의 거리를 만족하면
        	curr = bef; // curr 업데이트
            break;
        }
    }
}
path.push_back(A); // 시작점도 넣어줌
reverse(path.begin(), path.end()); // 뒤집으면 최단 경로를 담은 array가 됨

 

 

이번 글에서는 Dijkstra 알고리즘을 역추적하여 어떻게 최단 경로를 찾는지에 대해서 알아보았습니다. 다만, 이렇게 구한 최단 경로는 가능한 최단 경로들 중 하나만 찾습니다. (최단 경로는 여러 가지가 존재할 수 있습니다.)

 

다음에 다룰 알고리즘은 어떤 알고리즘일지 모르겠습니다. 또 생각나는게 있으면 다뤄보도록 할게요.

 

추천 문제

 

BOJ 11779 : 최소비용 구하기 2 - Dijkstra 역추적 기본 문제입니다. 위의 알고리즘을 그대로 적용하면 됩니다.

BOJ 31230 : 모비스터디 - 또 다른 Dijkstra 역추적 문제입니다만, 여기서는 최단 경로에 들어갈 수 있는 모든 정점들에 대해서 찾아보아야 합니다. 

BOJ 5719 : 거의 최단 경로 - 매우 유명한 Dijkstra 역추적 문제입니다. 최단 경로에 들어갈 수 있는 모든 간선들을 확인해봅시다.