우선순위 큐 다익스트라 알고리즘(Dijkstra Algorithm)

우선순위 큐 다익스트라 알고리즘의 코드 구현은 다음 책의 내용을 참조하였다.

http://book.naver.com/bookdb/book_detail.nhn?bid=7058764

923쪽, 다익스트라의 최단 거리 알고리즘의 구현

그리고 다익스트라 알고리즘이 진행되는 과정은 다음 게시물에 수록되어 있다.

http://www.crocus.co.kr/532 :: 다익스트라 개념

아래 내용을 통해 우선순위 큐 다익스트라 알고리즘의

개념 및 소스 코드를 확인하고, 이 코드를 이용해서 풀 수 있는 문제는 다음과 같다.

문제 원본 :: https://www.acmicpc.net/problem/1753

문제 풀이 :: http://programbasic.tistory.com/545

이 코드에서의 핵심은 다음과 같다.

1. priority_queue를 이용함으로써

즉, MinHeap(우선순위 큐)을 이용하여 시간 복잡도를 현저히 줄일 수 있게 되었다.

이때 log|V|가 되는 이유는 일반 다익스트라에서는 가장 최단 거리를 가진 정점을 찾기위해 선형 탐색을 이용하지만,

MinHeap을 이용하면 log|V|만에 최솟값이 가장 위로 올라오도록 정렬되기에 log|V|이다.

2. priority_queue에서는 기본적으로 가장 큰 원소가 pop의 우선순위를 가지기 때문에

가중치가 3, 2, 1이라는 값이 들어왔다면 우선순위는 3, 2, 1이아닌 1, 2, 3이어야 하기에

음의 가중치로 바꾸어 우선순위 큐에 넣는다.(-1, -2, -3으로)

3. A정점에서 B정점으로 가는 값이 이미 있는데 더 작은값이 생긴다면 

우선순위 큐에서 찾지 않고, 그냥 push한 후에, 나중에 가중치를 비교하여 

가중치가 더 큰 것이었다면 무시하도록 한다. 

아래 그림을 통해 우선순위 큐의 알고리즘이 어떻게 작동하는지 확인하자.

(a~d까지를 확인)

1) a번 정점에서 시작한다고 가정한다.

2) a번 정점은 시작점이므로 0의 최단 거리 값을 가지게 된다.

현재 dist 값 (a번 순서로 0,1,2,3 으로 간다고 가정)

dist[0] = 0

3) a번 정점에서 c번 정점으로의 최단 거리는 1임을 알 수 있다.

dist[0] = 0

dist[2] = 1

4) a번 정점에서 b번 정점으로의 최단 거리는 5임을 알 수 있다.

dist[0] = 0

dist[1] = 5

dist[2] = 1

5) a번 정점에서 가장 최단거리는 c이므로 c부터 방문한다.

dist[0] = 0

dist[1] = 5

dist[2] = 1

6) c번 정점에서 d까지의 최단거리는 3이다.

dist[0] = 0

dist[1] = 5

dist[2] = 1

dist[3] = 3

7) c번 정점에서의 방문이 끝났으니 그다음 가장 최단 거리를 가진 d번 정점을 방문한다.

dist[0] = 0

dist[1] = 5

dist[2] = 1

dist[3] = 3

8) d번 정점에서 b정점까지의 최단거리는 5에서 4로 변한다. 

dist[0] = 0

dist[1] = 4

dist[2] = 1

dist[3] = 3

여기서 아래의 코드에 의해 5가 아닌 4로 갱신됨을 알 수 있다.

8-1) 만약 d->b의 가중치를 4라고 하자.

a번 정점에서 b번 정점으로 갈 때 최단거리는 7이라고 알고있었지만,

a->b의 5라는 가중치가 존재하고 있다.

따라서 그림 아래의 알고리즘을 통해 비교가 된다.

결국 7 > 5이므로 업데이트 된다. (그림의 내용 참조)

 

현재 dist 값 (a번 순서로 0,1,2,3 으로 간다고 가정)

dist[0] = 0

dist[1] = 5 (7->5로 바뀜)

dist[2] = 1

dist[3] = 3

9) d번 정점에서 e정점까지의 최단거리는 8이다. 

dist[0] = 0

dist[1] = 4

dist[2] = 1

dist[3] = 3

dist[4] = 8

10) b번 정점에서 인접한 정점은 없으므로 그대로 있는다.

dist[0] = 0

dist[1] = 4

dist[2] = 1

dist[3] = 3

dist[4] = 8

11) e번 정점에서 인접한 정점은 없으니 그대로 있는다. 

dist[0] = 0

dist[1] = 4

dist[2] = 1

dist[3] = 3

dist[4] = 8

< 소스 코드 >

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
#include <cstdio>
 
#define MAX_V 20001
 
using namespace std;
 
// 그래프의 인접 리스트. (연결된 정점 번호, 간선 가중치) 쌍을 담아야 한다.
vector< pair<int, int>> adj[MAX_V]; // 정점의 최대 개수 :: MAX_V
 
vector<int> dijkstra(int src, int V, int E)
{
    // V만큼 배열을 INT_MAX로 초기화
    vector<int> dist(V, INT_MAX);
    dist[src] = 0; // 시작점은 0으로 초기화 한다. 
 
    priority_queue<pair<int, int> > pq;
 
    pq.push(make_pair(0, src)); // 시작점을 처음으로 우선순위 큐에 삽입
 
    while (!pq.empty())
    {
        // 우선순위 큐에 음의 가중치로 들어가 있으니 양으로 바꾸어준다.
        int cost = -pq.top().first; 
        int here = pq.top().second;
 
        pq.pop();
 
        // 만약 지금 꺼낸 것보다 더 짧은 경로를 알고 있다면 지금 꺼낸것을 무시한다.
        if (dist[here] < cost)
            continue;
 
        // 인접한 정점들을 모두 검사.
        for (int i = 0; i < adj[here].size(); i++)
        {
            int there = adj[here][i].first;
            int nextDist = cost + adj[here][i].second;
 
            // 더 짧은 경로를 발견하면, dist[]를 갱신하고 우선순위 큐에 넣는다.
            // dist 벡터에는 시작점 -> there 위치까지의 최단 거리가 담겨있다.
            if (dist[there] > nextDist)
            {
                dist[there] = nextDist;
                pq.push(make_pair(-nextDist, there));
                /*
                여기서 -로 넣는 이유?
                priority_queue STL은 기본적으로 가장 큰 원소가 위로 가도록 큐를 구성
                따라서 거리의 부호를 바꿔서 거리가 작은 정점부터 꺼내지도록 하기 위함
                */
            }
        }
    }
 
    return dist;
}