[알고리즘] 다익스트라 알고리즘

다익스트라 알고리즘

다익스트라 알고리즘은 그래프의 최단경로 탐색 알고리즘입니다. 이를 이용하면 음의 가중치가 없는 그래프의 한 정점에서 다른 모든 정점까지의 최단거리를 구할 수 있습니다. (음의 가중치가 있으며, 가중치의 합이 음수인 사이클이 없는 그래프의 경우 벨만-포드 알고리즘을 사용합니다.)

알고리즘을 간략하게 표현하면 다음과 같습니다.

1. 출발점으로부터의 최단거리를 저장할 배열 dist[]를 만든다. 출발점에는 0을, 다른 모든 정점에는 INF(큰 수)를 저장한다.

2. 현재 노드를 나타내는 변수 now에 출발 노드의 번호를 저장한다.

3. now로 부터 갈 수 있는 임의의 노드 next에 대해 dist[now] + edge[now][next]와 dist[next]를 비교한다.

4. 만약 dist[now] + edge[now][next]가 dist[next]보다 작다면 dist[next]의 값을 갱신한다.

5. now의 모든 이웃 노드에 대해 3~4 과정을 반복하고, now의 상태를 방문 완료로 바꾼다.

6. 미방문 상태의 노드 중, 출발점으로부터의 거리가 가장 짧은 노드를 하나 골라서 그 노드를 now에 저장한다.

7. 더이상 미방문 노드의 상태를 고를 수 없을 때 까지 3~6 과정을 반복한다.

알고리즘이 종료하면, dist[v]에는 출발점으로부터 v노드까지의 최단거리가 저장되어 있게 됩니다.

void dijkstra(int arr[MAX_N][MAX_N], int start, int dist[MAX_N]) {
    priority_queue< pair< int,int >> pq;

    for(int i=0;i< MAX_N;i++) {
        dist[i] = INF;
    }

    pq.push({0,start}); // {dist, destination}

    while(!pq.empty()) {
        int cur_dist = -pq.top().first;
        int cur_node = pq.top().second;
        pq.pop();

        for(int i=0;i< MAX_N;i++) {
            int nxt_dist = cur_dist +  arr[cur_node][i];

            if(nxt_dist < dist[i]) {
                dist[i] = nxt_dist;
                pq.push({-nxt_dist,i});
            }
        }
    }
}