[ALGOSPOT] ROUTING 신호 라우팅

ALGOSPOT ROUTING : http://www.playsw.or.kr/repo/cast/105

최단 경로 알고리즘 (다익스트라 알고리즘 Dijkstra Algorithm)을 이용

최단 경로 알고리즘 개념

참고 : http://www.playsw.or.kr/repo/cast/105

visit라는 vector를 정의하여 목적지 노드로 갈 수 있는 최소의 거리를 저장한다.

visit의 초기값은 무한대이므로 double의 최대인 DBL_MAX로 초기화한다.

1. 시작할 땐 noise에 있는 distance 값을 1.0으로 초기화 한다. -> 곱해야 자기 자신이 나올 수 있도록

   여기서 distance는 현재까지 이동한 값이다. 이 값에 간선의 가중치를 곱하여 visit의 값과 비교한다

   시작하는 index는 0

2. 시작하는 노드에 연결된 간선들 모두 방문한다

3. distance와 간선의 가중치를 곱한 값이 visit보다 작으면 갱신하고 noise라는 우선순위큐에 목적지까지의 최소 거리와 목적지의 노드의 index을 넣는다

4. 우선 순위 큐 noise가 비어있을 때까지 반복한다

5. 문제에서는 마지막 번호가 목적지로 설정해두었으므로 visit[visit.size()-1]을 return 한다

이중배열로 구현한다면 메모리 초과가 뜰 가능성이 있다

그러므로 인접 리스트를 vector를 이용하여 구현하였다

인접 리스트 인접 배열 개념

참고 : http://talksis.tistory.com/31

+)

priority_queue의 기준값은 첫번째 값이다 

예를 들어 priority_queue <pair<double,int>> max_heap;

double을 기준값으로 정렬된다

+) pair로 정의했다면 make_pair를 이용하여 push해야한다.

#include <iostream> #include <fstream> #include <vector> #include <queue> #include <algorithm> #include <functional> #include <float.h> using namespace std; #define NOTHING -1 #define VISITED 1 #define DIDNT_VISIT -1 #define MIN(X,Y) X<Y?X:Y vector<vector<pair<double, int>>> adj; priority_queue <pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> noise; vector<double>visit; //while문을 왜 계속 돌지 않을까? //min을 구하는 것이기 때문에 //크면 자동으로 들어가지 않음 -> 즉 visit[]안에 값을 저장하지만 크면 들어가지 않는 특징을 이용하여 visit대신 사용가능 double Dijkstra_Algorithm() { visit[0] = 1; //첫번째는 1로 해야 곱해도 자기자신이 나옴 //가장작은 noise와 그것의 index noise.push(make_pair(1.0, 0)); //priority_queue가 empty일때까지 while (!noise.empty()) { //proirity에서 noise가 가장 작은 값 double distance = noise.top().first; int index = noise.top().second; noise.pop(); if (distance > visit[index]) continue; //그 노드에 연결되어 있는 자식의 noise모두 확인 for (int j = 0; j < adj[index].size(); j++) { //현재 visit에 있는 값보다 priority에 있는 가장 작은 distance값*index의 자식들의 값 if (adj[index][j].first*distance<visit[adj[index][j].second]) { //갱신 visit[adj[index][j].second] = adj[index][j].first*distance; //queue에 삽입 noise.push(make_pair(visit[adj[index][j].second], adj[index][j].second)); } } } //맨 마지막 값 return return visit[adj.size() - 1]; } int main() { int For_Count, Node_Count, Edge_Count; cin >> For_Count; for (int i = 0; i < For_Count; i++) { cin >> Node_Count >> Edge_Count; adj = vector<vector<pair<double, int>>>(Node_Count); visit = vector<double>(Node_Count, DBL_MAX); int Node1, Node2; long double Edge; for (int j = 0; j < Edge_Count; j++) { cin >> Node1 >> Node2 >> Edge; adj[Node1].push_back(make_pair(Edge, Node2)); adj[Node2].push_back(make_pair(Edge, Node1)); } printf("%0.10f \n", Dijkstra_Algorithm()); } }