[Algorithm] 다익스트라(Dijkstra)

1. 다이나믹 프로그래밍을 활용한 대표적인 최단경로 탐색 알고리즘

2. 가중치 그래프에서, 임의의 점에서 목표점까지의 최소 비용 거리를 탐색할 수 있다.

3. 현재 점과 연결된 노드 중, 가중치가 가장 작은 노드를 선택 방문하여, 시작점으로부터 그 점까지의 거리를 업데이트 한다.

4. 3번 과정을 반복하면서, 특정 노드를 직접 방문했을 때 보다, 다른 점을 거쳐서 왔을 때의 거리가 작다면, 그 거리를 업데이트 하게 된다.

 

우선순위 큐 사용 알고리즘

1. 가중치 그래프를 저장하기 위한 구조체와 우선순위 큐(최소 힙)를 선언한다. 벡터를 사용해 구현할 시, 최소 가중치 노드를 찾기 위한 for loop 가 필요한데, 최소힙을 사용하면 이 과정을 O(log N)으로 줄일 수 있다.

2. 우선순위 큐에 시작점을 push 하고 연결된 모든 노드들에 대해 기존 거리보다 업데이트 되는 거리가 작다면(현재보다 새로 계산한 것이 거리가 작으므로 새로 푸쉬해야한다), 우선순위 큐에 push 한다.

3. 2번 과정을 우선순위 큐가 비어있을 때 까지 반복하면, 특정 점까지의 최단 거리를 얻을 수 있다.

4. 최단 거리 동안 거친 경로를 얻기 위해서는, prev[다음 노드] = 현재 노드, 방식으로 push 하는 과정에 추가해주면 도착점에서 시작점까지 거친 노드들을 추적할 수 있다. 

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

using namespace std;	

struct Edge {
    int vex; 
    int dis;
    Edge(int a, int b) {
        vex=a;
        dis=b;
    }
    bool operator<(const Edge &b) const {
        return dis > b.dis;
    }
};

int main(){
    ios_base::sync_with_stdio(false);

	freopen("dijkstra_pq.txt", "rt", stdin);
	priority_queue<Edge> pq;
    vector<pair<int, int> > graph[30];
    int i, n, m, a, b, c;
    cin >> n >> m;

    vector<int> dist(n+1, 2147000000);
    for (i=1; i<=m; i++) {
        cin>>a>>b>>c;
        graph[a].push_back(make_pair(b,c));
    }
    // Priority Queue Dikjstra
    pq.push(Edge(1, 0));
    dist[1] = 0;

    while (!pq.empty()) {
        int now = pq.top().vex;
        int cost = pq.top().dis;
        pq.pop();

        if (cost > dist[now]) continue;
        // 연결된 모든 노드들에 대해 탐색, 거리 업데이트 되면 PUSH
        for (i=0; i<graph[now].size(); i++) {
            int next = graph[now][i].first;
            int nextDist = cost + graph[now][i].second;

            if (dist[next] > nextDist) {
                dist[next] = nextDist;
                // 경로 노드 추적
                // prev[next] = now;
                pq.push(Edge(next, nextDist));
            }
        }
    }

    for (i=2; i<=n; i++) {
        if (dist[i] != 2147000000) cout << i << " : " << dist[i] << endl;
        else cout << i << " : impossible" << endl;
    }

	return 0;
}