다익스트라(Dijkstra) 알고리즘 - 최단거리

이번 시간에는 최단거리 알고리즘인 다익스트라(Dijkstra)에 대해 알아보자. 

다익스트라 알고리즘의 경우에는 크게 3개의 과정으로 나뉘게 된다. 

1) 체크되어 있지 않은 정점 중에서 dist의 값이 가장 작은 정점x를 선택한다.

2) x를 체크한다.

3) x와 연결된 모든 정점을 검사하며 간선을 (x,y,z)라고 했을 때 dist[y]>dist[x]+z 이면 갱신한다.

그런데 보통 1번과정에서 가장 dist값이 작은 경우를 찾는 과정을 효율적으로 구현하기 위해 priority_queue를 사용한다.

- priority_queue 자체가 max heap이기 때문에 -1을 곱해서 음수로 체크를 한다. 

for(int i=1;i<=n;i++){
    dist[i] = INF;
}
dist[s] = 0;
 
priority_queue<pair<int,int>> pq;
pq.push({0, s});
 
while(!pq.empty()){
    auto p = pq.top();
    pq.pop();
    int x = p.second;
    
    if(visited[x])continue;
    visited[x] = true;
    
    for(int i=0;i<v[x].size();i++){
        int y = v[x][i].first;
        if(dist[y]> dist[x]+v[x][i].second){
            dist[y]= dist[x]+v[x][i].second;
            pq.push({-dist[y],y});
        }
    }
}

코드를 살펴보게 되면 priority_queue를 통해 거리가 가장 짧은 거리를 쉽게 찾을 수 있고 , 그 경우에 (3)번 과정을 반복해주는 모습이다. 

만약 다익스트라 알고리즘을 통해 최단거리 경로를 찾기 위해서는 거리가 갱신이 될 때 prev배열에 그 위치를 저장해 주는 방식을 통해 역추적또한 가능하다.

for(int i=0;i<v[x].size();i++){
    int y = v[x][i].first;
    if(dist[y]> dist[x]+v[x][i].second){
        dist[y]= dist[x]+v[x][i].second;
        pre[y] = x;
        pq.push({-dist[y],y});
    }
}

 위와같이 prev배열에 갱신이 될 때 출발한 위치를 저장해두는 방식을 사용하여 역추적을 한다.