Dijkstra 다익스트라

다익스트라: 최단 경로 알고리즘

어떤 시작점에서 각 정점들까지의 최단 경로의 합을 구할 수 있다.

시작점 = src
vector<int> dist에 각 정점들의 비용이 저장되어 있다.

다익스트라의 구현은 set, priority_queue, for문을 통해 할 수 있다.
(밑의 소스는 pq를 사용)

[-] Collapse

#include<cstdio>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
int n, c;
vector<vector<pair<int, int> > > adj;
vector<int> dijkstra(int src){
    vector<int> dist(n, 987654321);
    dist[src] = 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;
            if (dist[there] > nextDist) {
                dist[there] = nextDist;
                pq.push(make_pair(-nextDist, there));
            }
        }
    }
    return dist;
}

adj[u][i].first = 정점 u와 연결된 i번째 정점을 의미
adj[u][i].second = 정점 u와 연결된 i번째 정점 사이의 비용

pq는 min_heap을 사용하기 위해 음수를 넣는다.

초기 거리는 INF를 넣는다.

if cost + next cost < dist[there] 이면 새로 갱신 후 pq에 추가

EX)

시작 점이 A일 때

이런 식으로 진행을 하게 되는데(다 할라 했는데 너무 많다 ㅎㅎ) 

쭉쭉 하다 보면 (5, B)가 pop이 될 때가 온다.

이 때는 dist[here] < cost이므로 그냥 pop만하고 continue문을 실행하게 된다.