Dijkstra 최단경로 알고리즘

#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
 
 
#define INF 987654321
#define MAX_E 300001
 
using namespace std;
 
typedef struct NODE {
    int end;
    int weight;
};
 
int dist[20000] = { 0, };
vector<NODE> map[MAX_E];
 
int start;
 
 
void dijkstra() {
 
    priority_queue <pair<int, int>> pq;
    pq.push({ 0,start }); //시작점 삽입
 
    while (!pq.empty()){//큐가 빌때까지 반복 
        int now_node = pq.top().second; 
        int cost = -1 * pq.top().first;
        pq.pop(); //제일 우선순위 높은 ... (?) 노드 삭제
 
        for (int k = 0; k < map[now_node].size(); k++) { //now_node에 연결된 정점 체크
        
            int new_val = dist[now_node] + map[now_node][k].weight; 
            int before_val = dist[map[now_node][k].end];
 
            if (new_val < before_val) {
                dist[map[now_node][k].end] = new_val;
                pq.push({ -1 * new_val , map[now_node][k].end });
            } // 간선 weight 갱신
            
 
        }
    }
 
}
 
int main() {
 
    int v, e; //v:정점 e:간선
    
    int from, to, w;
 
    int i, j;
 
    scanf("%d %d", &v, &e);
    scanf("%d", &start); //시작점
 
    for (i = 1;i <= e;i++) {
        scanf("%d %d %d", &from, &to, &w);
        map[from].push_back(NODE{to,w});
    }
 
    for (i = 1;i <= v;i++) {
        dist[i] = INF;
    }
 
    dist[start] = 0;
 
    dijkstra();
 
 
    for (i = 1;i <= v;i++) {
        if (dist[i] != INF) printf("%d\n", dist[i]);
        else printf("INF\n");
    }
 
    return 0;
}
 

처음에 map 벡터에 연결된 정점들과 해당 weight를 저장해준다.

우선순위 큐는 min_heap ! (weight이 작은것부터 방문하는 이유)

* 우선순위 큐는 기본적으로 큰 원소가 pop의 우선순위를 가지기 때문에,

음의 가중치로 바꾸어 우선순위 큐에 넣는다. (-1을 곱하는 이유)

  ex) weight이 10, 9, 8 이라는 값이 들어왔다면 우선순위는 1 2 3 이어야함.