[ 알고리즘 / 그래프 / 최단 경로 탐색 ] 다익스트라(Dijkstra) 알고리즘

그래프의 정점끼리의 최단 경로를 구하는 문제

1) 하나의 정점에서 다른 하나의 정점까지의 최단 경로를 구하는 문제 (1:1)

2) 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제 (1:N)

3) 하나의 목적지로 가는 모든 최단 경로를 구하는 문제 (N:1)

4) 모든 최단 경로를 구하는 문제 (N:N)

 

다익스트라 알고리즘은 간선에 가중치가 있는 그래프에서 1:N 최단거리를 구하는 알고리즘이다.

사이클이 없는 방향성 그 래프에 한해서만 사용할 수 있다.

 

1. 다익스트라 알고리즘?

1. Dist[] 배열에 시작점으로부터 자신에게 이르는 경로의 길이를 ∞(무한대)로 초기화
2. 시작 정점의 경로 길이를 0으로 초기화하고(시작 정점 -> 시작 정점 거리는 0)  + 방문한 정점으로 체크
3. 방문한 정점들과 연결되어 있는 정점들 중 비용이 가장 적은 정점부터 선택하여, 해당 정점까지의 현재 경로 길이가 Dist[]에 저장된 경로 길이보다 짧으면 값 갱신 + 해당 정점을 방문한 정점으로 체크
4. 그래프 내의 모든 정점이 최단 경로에 소속될 때까지 (3)과정을 반복

 

너비 우선 탐색과 비슷해보이는 알고리즘이다.

하지만 너비 우선 탐색의 경우, 큐(Queue)를 사용하여 인덱스 기준으로 인접한 정점을 방문하기 때문에 가중치가 없다면 가장 짧은 거리를 찾아낼 수 있다. 하지만 가중치가 있는 그래프에서 최단 거리를 찾을 때, S -(2)-> A -(4)-> B -(3)-> C : 9 일 경우와  S -(12)-> C : 12 의 경우 후자의 결과를 내놓을 것이다.

 

이를 다익스트라 알고리즘에서는 우선순위 큐(Prior_Queue)를 사용하여 해결한다. 우선순위 큐에 정점의 번호와 함께 지금까지 찾아낸 해당 정점까지의 최단 거리를 쌍으로 넣는다.

 

각 정점을 방문할 때마다 인접한 정점을 모두 검사한다. 간선(u, v)를 검사했는데, v가 아직 방문하지 않은 정점이라고 치자. 그러면 u까지의 최단 거리에 (u, v)의 가중치를 더해 v까지의 경로의 길이를 찾는다. 그리고 그 길이를 Dist[v]에 갱신한다. 이 때 주의할 점은 기존의 Dist[v] 값보다 작을 때 갱신해야 한다는 점이다. 기존의 Dist[v] 값이 더 작다면, 이전에 발견한 경로가 더 짧은 경로라는 것이기 때문에 현재 경로의 길이를 무시하면 된다. 그 후 (Dist[v], v)를 큐에 넣어주며 반복한다.

 

2. 한계

단, 다익스트라를 포함한 위에서 제시한 알고리즘들은 가중치가 음수 일때는 사용하지 못한다.

가중치가 음수일 경우 벨만포드 알고리즘(O(VE))이나 SPFA(O(VE))를 통하여 최단거리를 구해주어야 한다.

 

3. 구현

void Dijkstra()
{
    priority_queue<pair<int, int>> PQ;
    PQ.push({ Start, 0 }); // { 정점 idx, 해당 정점까지의 최단거리 }
    Dist[Start] = 0;
    
    while (!PQ.empty())
    {
        int Cur = PQ.top().first;
        int Cost = -PQ.top().second;
        PQ.pop();
        
        // 이미 현재 Cost보다 Cur의 더 짧은 경로를 찾았다면 무시
        if(Dist[Cur] < Cost) continue;
        
        // 인접한 정점을 모두 검사
        for(int i = 0; i < Adj[Cur].size(); i++)
        {
            int Next = Adj[Cur][i].first;
            int NCost = Adj[Cur][i].second;
            // 인접한 접점까지 가는 더 짧은 경로를 찾은 경우 값을 갱신하고 우선순위 큐에 넣음
            if(Dist[Next] > NCost + Cost)
            {
                Dist[Next] = NCost + Cost;
                PQ.push({ Next, -Dist[Next] });
            }
        }
    }
}

 

비용에  -값을 붙여서 우선순위 큐에 넣는 이유

우선순위 큐는 '값이 클 수록 더 높은 우선순위'를 갖게 되기 때문에 -값을 붙여 값의 우선순위를 반전시켜 준다.