그래프 - 우선순위 큐를 활용한 다익스트라 알고리즘

#include <iostream>
#include <vector>
#include <queue>

#define INF 123456789
using namespace std;

vector<pair<int, int>> adj[20001];                //인접리스트
int table[20001];                                           //비용을 갱신할 테이블

 

void dijkstra(int start) {
    priority_queue<pair<int, int>> pq;     

    //큐에 들어있는 원소의 의미는 <시작 지점으로부터의 비용, 정점>이다.

    //이때, 비용은 절댓값이 같은 음수로 저장되어있다. (e.g. 비용이 5라면 큐에는 -5로 저장되어있음.)

    //그 이유는 기본적으로 큐의 원소인 pair가 사전순(first->second) 기준으로 내림차순 삽입되기 때문이다.

    //즉, 예를들어 5, 3, 7의 비용이 있다면 이것이 7, 5, 3이 아닌 -3, -5, -7 순으로 삽입되도록 비용을 절댓값이 같은 음수로 저장한다.

    fill_n(table, 20001, INF);                    //테이블에서 비용을 모두 무한대로 셋팅함
    table[start] = 0;                                  //시작위치는 비용을 0으로 함

    pq.push({ 0, start });                           //큐에 <비용(0), 시작지점(start)>을 삽입 

    while (!pq.empty()) {

        //큐에서 새로운 원소를 뽑는다. 당연히 이는 큐에 들어있는 원소들 중 시작 지점으로부터의 비용이 가장 작은 값이다.
        int cost = -pq.top().first;                //그리고 음수로 저장되어있으니 다시 양수로 바꾼다.
        int vert = pq.top().second;
        pq.pop();

        if (table[vert] < cost) continue;     //이미 table 배열에 큐에서 방금 뽑은 비용보다 더 작은 비용이 저장되어 있다면 무시한다.

        for (int i = 0; i < adj[vert].size(); i++) {               //방금 뽑은 새로운 정점과 연결된 모든 정점들에 대하여
            int newCost = cost + adj[vert][i].second;      //뽑은 정점을 거쳐서 도착할때의 비용을 계산한다.
            if (newCost < table[adj[vert][i].first]) {           //그리고 이 비용이 기존에 저장된 비용보다 더 작다면 갱신한다.
                table[adj[vert][i].first] = newCost;
                pq.push(make_pair(-newCost, adj[vert][i].first));    //새롭게 갱신된 값을 큐에 넣어준다.
            }
        }
    }
}