-
다익스트라(dijkstra)SCCC - Soongsil Computing Contest Club/2019 Spring-Study 2019. 6. 3. 01:25반응형
1. 다익스트라
특정 하나의 노드에서 각 노드까지의 최단길이를 모두 구하는 알고리즘.
<1> 제일 작은 노드 탐색
<2> 갈 수 있는 노드들 값 갱신이거 1,2 무한반복 : 다익스트라. 쉽죠?
일종의 그리디라고 할 수 있는 다익스트라. 그리디의 모순에 의한 증명으로 증명 할 수 있다.
>>위의 알고리즘을 사용해서 최단경로를 만들었을 때 다른 노드를 경유하여 들어오는 경로가 최단이지 않으면 증명 완료.
대표적인 다익스트라 문제
https://www.acmicpc.net/problem/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; }
반응형'SCCC - Soongsil Computing Contest Club > 2019 Spring-Study' 카테고리의 다른 글
STL Vector, 그래프, 트리 (20190517) (1) 2019.05.17 STL Priority_queue(heap), (20190503) (0) 2019.05.03 시간복잡도와 STL (20190412) (0) 2019.04.12