1:N 최단 거리 알고리즘 다익스트라 (Dijkstra algorithm)

목표 : 다익스트라 알고리즘에 대해 이해하고 코딩할 수 있다.

다익스트라 알고리즘은 그래프에서 한 노드에서 다른 노드 사이의 최단 거리를 구하는 알고리즘입니다.

다익스트라 알고리즘의 특징

1. 음의 가중치를 가지면 안됨.

2. 무향, 유향 그래프 모두 가능함

3. 우선순위 큐를 배열로 구현한다면 O(V^2)

4. 힙으로 구현한다면 O(ElogV)

유사한 알고리즘으로 A*알고리즘, 플로이드-워셜 알고리즘이 있음

1. 출발 노드로부터 최단거리를 저장할 배열 dist[E + 1] 을 만들고 출발 노드에는 0을 나머지 노드에는 INF 의 값으로 초기화한다.

2. 현재 노드 here을 출발 노드라고 저장한다.

3. here 에서 갈 수 있는 노드를 There 라고 할 때, dist[here] + arr[here][there] 와 dist[there]을 비교함

4. dist[here] + arr[here][there]  < dist[there] => dist[there] = dist[here] + arr[here][there]

5. 모든 갈 수 있는 노드에 대해 이 과정을 한다 (4의 과정)

6. here을 visited 하고 visited 되지 않은 there 에 대해 반복한다.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <string>
#include <queue>
using namespace std;
priority_queue< pair < int , int > > PQ;
vector < vector < pair< int, int > > > arr;
vector<int> dist;

int main() {
    freopen("input.txt","r",stdin);
    int V,E;
    int start;
    int u,v,w;
    
    cin>>V>>E>>start;
    arr.resize(V+1,vector < pair< int, int > >());
    for(int i=0;i<E;i++) {
        cin>>u>>v>>w;
        arr[u].push_back(make_pair(v, w));  //u->v 가중치 w
    }
    
    dist.resize(V+1,100000000);
    PQ.push(make_pair(0, start));
    
    while(!PQ.empty()) {
        int d=-PQ.top().first;
        int here=PQ.top().second;
        PQ.pop();
        
        if(dist[here]<=d)
            continue;
        
        dist[here]=d;
        
        for(int i=0;i<arr[here].size();i++) {
            if(arr[here][i].first<100000000) {
                int there=arr[here][i].first;
                int nextadd=arr[here][i].second+d;
                PQ.push(make_pair(-nextadd,there));
            }
        }
    }
    
    return 0;
}