다익스트라(Dijkstra)

https://youtu.be/611B-9zk2o4

https://blog.naver.com/ndb796/221234424646

주의할 점은 

first에는 거리(비용, 가중치 등)를

second에는 정점이 들어가야 한다.

우선순위 큐 pair에서는 first를 우선 비교하는데, 

first에 정점이 들어가면 아무 소용없는 정점이 큰 것부터 위에 온다.

물론 애초에 pair 자체가 first를 우선순위로 한다.(비교 등등 부분에서)

출발점 : 1
 
[1] → [1] 최소 비용 : 0
[1] → [2] 최소 비용 : 2
[1] → [3] 최소 비용 : 3
[1] → [4] 최소 비용 : 1
[1] → [5] 최소 비용 : 2
[1] → [6] 최소 비용 : 4

#include <bits/stdc++.h>
 
using namespace std;
 
#define MAX 7
#define INF 2e9
 
int dist[MAX];
 
vector<pair<int, int> > v[MAX];
 
void dijkstra(int start)
{
    priority_queue<pair<int, int> > pq; // 기본적으로 최대힙(큰 값이 위로)
    dist[start] = 0; // 출발점
    pq.push({ 0, start }); // { 정점, 거리 }
 
    while (!pq.empty())
    {        
        int distance = -pq.top().first; // 음수
        int current = pq.top().second;
 
        pq.pop();
 
        if (dist[current] < distance) continue; // 이미 최단거리면 무시
 
        for (auto i : v[current])
        {
            int nextDistance = i.first;
            int next = i.second; // start → current → next
 
            /*
            dist[next] : start → next까지의 최단 거리
            start → next까지의 거리(=dist[next])보다
            start → current → next까지의 거리 합(=dist[current] + nextDistance)이
            더 짧으면, 갱신한다.
            */
 
            // start → next vs start → current + current → next
            if (dist[next] > dist[current] + nextDistance) // 더 짧으면 갱신
            {
                dist[next] = dist[current] + nextDistance;
                pq.push({ -dist[next], next });
            }
        }
    }
}
 
int main(void)
{
    fill(dist, dist + MAX, INF);
 
    v[1].push_back({ 2, 2 });
    v[1].push_back({ 5, 3 });
    v[1].push_back({ 1, 4 });
                      
    v[2].push_back({ 2, 1 });
    v[2].push_back({ 3, 3 });
    v[2].push_back({ 2, 4 });
                      
    v[3].push_back({ 5, 1 });
    v[3].push_back({ 3, 2 });
    v[3].push_back({ 3, 4 });
    v[3].push_back({ 1, 5 });
    v[3].push_back({ 5, 6 });
                      
    v[4].push_back({ 1, 1 });
    v[4].push_back({ 2, 2 });
    v[4].push_back({ 3, 3 });
    v[4].push_back({ 1, 5 });
                      
    v[5].push_back({ 1, 3 });
    v[5].push_back({ 1, 4 });
    v[5].push_back({ 2, 6 });
                      
    v[6].push_back({ 5, 3 });
    v[6].push_back({ 2, 5 });
 
    dijkstra(1);
 
    printf("출발점 : 1\n\n");
 
    for (int i = 1; i < MAX; i++)
        printf("[1] → [%d] 최소 비용 : %d\n", i, dist[i]);
 
    return 0;
}