[최단 경로] 다익스트라

 

우선순위 큐를 사용하는 너비 우선 탐색

우선순위 큐 <- (정점의 번호, 해당 정점까지의 최단 거리)

 

|E| = 간선의 개수

|V| = 정점의 개수

시간 복잡도 : O(|E|lg|V|)

 

/*
	코드 출처 : 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략2, 인사이트, 구종만
*/
#include <queue>
#include <vector>
#include <functional>
#include <iostream>

constexpr int INF = 987654321;

//정점의 개수와 정점의 번호가 다름을 주의, 정점이 5개라고 0~4 혹은 1~5로 번호가 매겨진다는 보장은 없음
int V; //정점의 개수
vector<pair<int, int>> adj[V]; //인접 리스트, (연결된 정점 번호, 가중치)

vector<int> dijkstra(int src) {
    vector<int> dist(V, INF);
    dist[src] = 0;
    //priority_queue는 디폴트가 내림차순이므로 오름차순으로 바꿔주기 위한 선언
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<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;
            
            if(dist[there] > nextDist) {
                dist[there] = nextDist;
                pq.push(make_pair(nextDist, there));
            }
        }
	}
    return dist;
}