다익스트라(dijkstra)

1. 다익스트라

특정 하나의 노드에서 각 노드까지의 최단길이를 모두 구하는 알고리즘.

 <1> 제일 작은 노드 탐색
 <2> 갈 수 있는 노드들 값 갱신

이거 1,2 무한반복 : 다익스트라. 쉽죠?

일종의 그리디라고 할 수 있는 다익스트라. 그리디의 모순에 의한 증명으로 증명 할 수 있다.

  >>위의 알고리즘을 사용해서 최단경로를 만들었을 때 다른 노드를 경유하여 들어오는 경로가 최단이지 않으면 증명 완료.

 

대표적인 다익스트라 문제

https://www.acmicpc.net/problem/1753

1753번: 최단경로

 

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>

#define INF 987654321
using namespace std;
struct node{
    int weight, next;
    node(int next, int weight) : weight(weight), next(next) {}
};
struct pqdata{
    int nd, dis;
    pqdata(int nd, int dis) :nd(nd), dis(dis) {}
};
bool operator<(node a, node b){
    return a.weight > b.weight;
}
bool operator<(pqdata a, pqdata b){
    return a.dis>b.dis;
}
int V,E,K;
vector<node> vv[300001];
int dist[300001];
priority_queue<pqdata> pq;
int main(){
    scanf("%d %d %d", &V, &E, &K);
    for(int i=0; i<E; ++i){
        int u,v,w;
        cin >> u >> v >> w;
        vv[u].push_back(node(v,w));
    }
    for(int i=1; i<=V; ++i){
        dist[i]=INF;
    }
    dist[K]=0;
    for(int i=1; i<=V; ++i){
        pq.push(pqdata(i, dist[i]));
    }
    while(!pq.empty()){
        pqdata data=pq.top();
        pq.pop();
        if(dist[data.nd]!=data.dis){
            continue; // why?
        }
        for(int i=0; i<vv[data.nd].size(); ++i){
            int nd = vv[data.nd][i].next, nw = vv[data.nd][i].weight;
            if(dist[nd] > data.dis + nw){
                dist[nd] = data.dis + nw;
                pq.push(pqdata(nd, dist[nw]));
            }
        }
    }
    for(int i=1; i<=V; ++i){
        if(dist[i]==INF) printf("INF\n");
        else printf("%d\n", dist[i]);
    }
    return 0;
}