다익스트라 알고리즘 : 한 정점에서 다른 정점들로 가는 최단경로를 구하는 알고리즘
<시간 복잡도>
그냥 기본적인 알고리즘은 노드를 선택할 때 계속 최단 거리의 노드를 찾아주어야 하기에 O(n^2) 시간복잡도가 걸린다.
그렇기에 넣을 때 logn시간이 걸리는 priority_queue를 사용하면 O(nlogn)시간 복잡도로 줄일 수 있다. 그렇기에 현재 코드는 priority_queue로 구현 하였다.
<전체적인 알고리즘>
1. 시작노드에서부터 해당 노드로의 최단 거리(배열에 저장된 거리) 중 가장 짧은 노드 선택.(전에 선택된 것들 제외)
2. 선택된 노드에서부터 다음 노드로 가는 경로가 배열에 저장된 최단 경로보다 작으면 갱신
3. 1-2를 끝날 때까지 반복
<경로 찾는 알고리즘>
1. 최단 거리가 갱신될 때마다 pre배열에 그 전 노드를 기록해둠.
2. 나중에 재귀 함수로 그 전 노드들을 계속 탐색하면 결국 시작노드까지의 경로가 발견됨.
<전체 코드>
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 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 | #include<iostream>#include<queue>#include<vector>using namespace std;int n = 5;vector<pair<int,int>> a[7];int INF = 987654321;int d[7];int pre[7];void dijkstra(int start){ fill(&d[0], &d[7], INF); //각 정점 거리 무한대로 셋팅 priority_queue <pair<int, int>> pq; //정점 중에 거리가 최소인 정점부터 갱신해야 하기 때문에 pq.push(make_pair(0, start)); d[start] = 0; while(!pq.empty()) { int node = pq.top().second; int distance = -pq.top().first; //거리에 -를 붙어야 최소인 거리부터 정렬됨 pq.pop(); if (distance > d[node])continue; for (int i = 0; i < a[node].size(); i++) { int next = a[node][i].first; int nextdistance = a[node][i].second + distance; if (nextdistance < d[next]) //현재 노드로 부터 가는 거리가 더 짧으면 갱신 { d[next] = nextdistance; pre[next] = node; pq.push(make_pair(-nextdistance, next)); } } }}void path(int node) // 현재 노드의 전 노드를 확인하며 경로 찾기{ if (node != pre[node])path(pre[node]); printf("%d ", node);}int main(){ for (int i = 1; i <= n; i++) { pre[i] = i; } a[1].push_back(make_pair(3,6)); //그래프 셋팅 a[1].push_back(make_pair(4, 3)); a[2].push_back(make_pair(1, 3)); a[3].push_back(make_pair(4, 2)); a[4].push_back(make_pair(2, 1)); a[4].push_back(make_pair(3, 1)); a[5].push_back(make_pair(2, 4)); a[5].push_back(make_pair(4, 2)); int start = 5; dijkstra(start); //5에서 시작할 경우 printf("시작노드는 %d\n\n", start); for (int i = 1; i <= n; i++) { printf("노드 %d로의 최단거리 : %d\n", i, d[i]); } cout << "\n"; for (int i = 1; i <= 5; i++) { printf("노드 %d로 가는 최단 경로 : ",i); path(i); cout << "\n"; } return 0;} |
궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.
반응형