백준 1753 : 최단경로

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

최단경로 기본문제.

한 정점을 기준으로 다른 정점까지 최단 경로를 구할때 만약 간선의 가중치가 없으면 BFS로 탐색하면 된다.

만약 간선의 가중치가 존재하면 기본적으로 다익스트라(Dijkstra) 알고리즘을 사용할 수 있다.

다익스트라 알고리즘은 BFS와 형태가 유사한데

while문에 queue 대신 priority_queue를 넣고 너비우선탐색처럼 정점을 순회하며

각 정점의 최단경로를 갱신하는 방법이다. 

(priority_queue를 쓰는 것은 다익스트라 알고리즘을 ElogV 로 최적화 한 것이다.)

각 정점에 연결된 간선의 정보를 넣고 다음 정점을 탐색할때 만약 

(다음 정점의 Distance > 현재정점의 Distance + 간선의 가중치) 이면

다음 정점의 Distance 를 현재정점의 Distance+간선의 가중치로 최소값을

갱신해주고 다음 정점을 우선순위 큐에 넣는다.(이때 우선순위 큐의 정렬은 각 정점의 거리를 오름차순으로 정렬한다.)

 * 이때 유의해야 할 것은 우선순위 큐와 Sort 할때 compare 함수가 다르다는 것이다.

sort 할때는 연산자 오버로딩을

bool operator < (const Edge &e) const{

return dist < e.dist;

}

다음과 같이 지정해주면 오름차순 정렬이 된다.

그러나 priority_queue는 큐와는 달리 front가 아니라 top에서 자료를 빼온다.

따라서

bool operator < (const Edge &e) const{

return dist > e.dist;

}

처럼 반대로 연산자를 지정해줘야 우선순위 큐에서 작은 순서대로 값을 뺄 수 있다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

#include <iostream> #include <vector> #include <queue> #define MAX 20001 #define INF 1000000000 using namespace std; int v, e, init; struct Vertex{ int idx, dist = INF; vector<pair<int, int>> next; bool operator < (const Vertex &v) const{ return dist > v.dist; } }; Vertex vertex[MAX]; void dijkstra(){ priority_queue<Vertex> pq; pq.push(vertex[init]); while(!pq.empty()){ Vertex curVertex = pq.top(); pq.pop(); for(pair<int, int> pa : curVertex.next){ if(vertex[pa.second].dist > curVertex.dist + pa.first){ vertex[pa.second].dist = curVertex.dist + pa.first; pq.push(vertex[pa.second]); } } } } void rPrint(){ for(int i = 1; i <= v; i++){ if(vertex[i].dist >= INF){ cout << "INF" << '\n'; continue; } cout << vertex[i].dist << '\n'; } } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> v >> e >> init; for(int i = 1; i <= v; i++){ vertex[i].idx = i; } vertex[init].dist = 0; while(e--){ int u, v, w; cin >> u >> v >> w; vertex[u].next.push_back(make_pair(w, v)); } dijkstra(); rPrint(); return 0; }