다익스트라 알고리즘(Dijkstra algorithm)

Dijkstra algorithm

Dijkstra Algorithm

- 그래프 자료구조에서 노드 사이의 최단 경로를 찾는 알고리즘

- 음의 가중치가 없는 그래프에서 한 노드에서의 모든 노드까지의 최단거리를 구하는 알고리즘

- O(E*logV)의 시간복잡도를 가짐

- 초창기에는 O(V^2)의 시간 복잡도를 가졌지만 우선순위 큐를 사용하는 방식이 생기면서 O(E*logV)의 시간복잡도로 더 개선된 알고리즘이 되었다.

-> O(E*logV)의 시간 복잡도를 가지는 우선순위 큐를 사용하는 방식을 설명하려 한다.

Dijkstra Algorithm Logic

- 한 정점(노드)를 선택한다.

- 아직 확인되지 않은 노드의 cost는 무한대로 초기화 시킨다.

- cost가 적은 node들을 방문하며 모든 노드까지의 최단 경로를 찾는다.

비교적 이론적으로는 간단해보인다.

다음 그림에서 A가 선택된 노드라고 생각하고 Logic을 설명하려 한다.

먼저 자기 자신으로 가는 cost는 0으로 초기화해주고 인접노드를 제외한 노드들을 모두 무한대값으로 초기화해준다.

A->B까지 가는 경로가 2로 최소이기 때문에 B를 방문하고 B를 2로 기록한다.

B->C는 A->B->C이므로 7, B->E는 A->B->E이므로 6으로 본다.

그 다음은 최소 값이 A->D, 3이므로 D를 방문하고 기록해준다.

여기서 D->E도 갈 수 있지만 A->B->E의 경로보다 cost가 높기 때문에 생각하지 않는다.

그 다음으로 최소 값인 E를 방문해준다. 이러한 방식으로 계속해서 진행 해가면서 모든 node를 방문해 A에서의 모든 노드까지의 최단 경로를 알 수 있다.

계속해서 진행하며 다음과 같이 모든 노드를 방문해 cost를 기록할 수 있다.

모든 Node로 방문한 후에 다음과 같은 table로 작성할 수 있을 것이다.

A에서 모든 node로 갈수 있는 최소비용을 나타내는 table로 작성할 수 있다.

Dijkstra Algorithm Source Code

- 위의 Logic에서 설명한 예제를 소스코드로 구현해보았다.

A - 1, ....  , G - 7로 바꾸어 구현했다.

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

#include <iostream> #include <algorithm> #include <functional> #include <vector> #include <queue> using namespace std;   #define INF 2100000000 priority_queue <pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;    // priority queue 선언   vector<pair<int,int>> graph[8];                            // 각 노드에서 갈 수 있는 노드와 cost를 기록해주기 위함                                                         // first : cost, second : node 번호 int fromnode, tonode, cost, startnode,n_cost,n_node; int cost_arr[8];                                        // start node에서 각 node로 갈 수 있는 최소 비용을 기록할 array   int main() {     for (int i = 0; i < 9; i++) {                // 무방향 그래프이므로 노드,노드,cost 입력받은 후 양 방향에서 갈 수 있게 넣어줌         cin >> fromnode >> tonode >> cost;         graph[fromnode].push_back(make_pair(cost, tonode));         graph[tonode].push_back(make_pair(cost, fromnode));     }       for (int i = 1; i < 8; i++) {                // 처음에 모두 무한대 값으로 초기화해줌         cost_arr[i] = INF;     }     cin >> startnode;     cost_arr[startnode] = 0;                    // 시작 노드로 가는 cost 0으로 초기화          pq.push(make_pair(cost_arr[startnode], startnode));        // startnode로 가는 cost와 startnode 번호를 priority queue에 넣어줌       while (!pq.empty()) {         n_cost = pq.top().first;        // 가장 작은 cost를 가진 top을 꺼내옴         n_node = pq.top().second;        // 가장 작은 cost를 가진 노드의 번호를 꺼내옴           pq.pop();                        // queue에서 제거         if (n_cost > cost_arr[n_node]) {    // 새로 꺼내온 것보다 기존 것이 더 작을 경우 넘어감             continue;         }         for (int j = 0; j < graph[n_node].size(); j++)        // 꺼내온 노드에서 갈수 있는 모든 node를 탐색         {             if (n_cost + graph[n_node][j].first < cost_arr[graph[n_node][j].second])        // startnode에서 현재 node까지의 거리+ 현재 node에서 다른 node로 가는 cost             {                                                                                // 가 현재까지 기록된 최소 비용보다 작을 경우                 cost_arr[graph[n_node][j].second] = n_cost + graph[n_node][j].first;            // cost array에 최소 비용 기록                 pq.push(make_pair(n_cost + graph[n_node][j].first, graph[n_node][j].second));    // priority queue에 넣어줌             }         }     }     for (int i = 1; i < 8; i++) {         cout << (char)(startnode + 64) << "->" << (char)(i + 64) << " cost : " << cost_arr[i] << endl;     }     return 0; } Colored by Color Scripter

cs

- priority_queue에 cost를 음수로 넣어주는 방법도 있지만 greater를 사용하여 최소값이 top으로 가게 구현

- 초기화 단계에서 시작노드까지의 거리를 0으로 초기화, 나머지는 무한대(INF)로 초기화

- priority queue에 넣어주고 하나씩 꺼내며 최단 경로를 찾아가는 방법으로 구현

- 시작노드에서 현재 노드 까지의 cost+현재 노드에서 새로운 노드까지 가는 cost 가 현재 구해놓은 새로운 노드까지의 거리보다 작을 경우 priority queue에 넣어 update시켜주게 구현

실행 결과

위와 같이 노드 번호, 노드 번호, cost를 입력하고 시작 노드를 입력하면 시작 노드에서 모든 노드로 가는 최단 경로를 출력해주게 만들었다.