Dijkstra Algorithm

다익스트라 알고리즘은 양의 가중치만 있는 그래프에서 어떤 정점으로부터 모든 정점까지의 최소 거리를 구하는 알고리즘이다. 다익스트라 알고리즘은 최단거리를 구할 때 매우 유용해서 GPS등에서도 사용한다고 한다(정확히는 모르지만,,). 

쉽게 설명되어있는 유튜브 영상 : https://www.youtube.com/watch?v=EFg3u_E6eHU

 

 아주 예전에 다익스트라 알고리즘을 처음 알았을 때 아주 똑똑한 친구가 위의 영상을 추천해줘서 봤었다. 이해하기 쉽게 설명되어있어서 다익스트라 알고리즘을 배우려고 하거나 까먹었을 때 보면 좋은 영상이다. 

 

1. 다익스트라 작동 과정

다익스트라는 다음과 같이 작동한다.

1) pair형태로 {0, 시작정점}을 priority queue에 넣는다.
2) priority queue가 빌 때까지 3)~5) 반복
3) priority queue의 top 빼내기
4) 3)의 노드와 연결된 모든 간선들을 탐색하며 최단거리 업데이트
5) 4)에서 최단거리가 업데이트된 모든 정점들과 그 정점들까지의 최단거리를 pair형태로 priority queue에 넣는다.

 priority queue를 쓰는 이유는 간선의 가중치가 가장 작은 것을 빠르게 사용하기 위해서이다. 시간복잡도는 간선의 개수를 $E$라고 할 때 4)에서 모든 간선이 탐색될 경우가 있으므로  $O(E)$ 이고, priority를 사용할 때 $O(logE)$ 가 걸리므로 최종적으로 $O(ElogE)$ 가 된다. $E\leq V^2$ 이므로 $logE \leq 2logV$ 여서 $O(ElogV)$ 로 표기하기도 한다.

 

2. 다익스트라 구현

void Dijkstra(int Start){
    minDistance[Start] = 0;
    priority_queue<pair<int,int>> pq;
    pq.push({0,Start});
    while(!pq.empty())
    {
        int current = pq.top().second;
        int distance = -pq.top().first;
        pq.pop();
        for(int i=0;i<graph[current].size();i++)
        {
            int next = graph[current][i].first;
            int nxDistance = distance + graph[current][i].second;
            if(nxDistance < minDistance[next]){
                minDistance[next] = nxDistance;
                pq.push({-nxDistance,next});
            }
        }
    }
}

 여기서 $Start$는 시작 정점이고, $minDistance$ 배열은 시작정점으로부터 다른 정점들로 까지의 최단거리를 저장하는 배열이다.