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

다익스트라 알고리즘은 최단거리 (shortest path) 탐색 알고리즘의 일종으로, DP에 기반한 알고리즘이다.

한 node에서 다른 모든 node 까지의 최단거리를 탐색할 수 있다.

각 노드간 간선이 존재하고, 각 간선의 거리가 주어질 때 최단 거리를 구할 수 있다.

 

다음과 같은 그래프가 있다고 가정한다.

Node 1에서 각 노드까지의 거리를 표로 정리하면 다음과 같다.

노드	1	2	3	4	5	6
거리	0	2	5	1	INF	INF

노드 1에서 5,6까지는 바로 갈 수 없으므로 무한으로 가정한다.

이때 1에서 가장 가까운 노드는 4이다.

따라서 node 4를 거칠 경우 1에 대한 최단 거리를 먼저 구한다.

4를 거쳐 갈 수 있는 노드는 3,5 인데,

1-4-3으로 3까지 갈 경우 거리는 1+3 = 4이다.

이때 1-3 으로 갈 경우 거리는 5이므로, 1에서 3까지의 최단 거리는 4이다.

따라서 표를 바꿔준다.

또한 1-4-5로 5까지 갈 경우 거리는 1+1 = 2이다.

따라서 1에서 5까지의 최단 거리는 2이다.

업데이트 된 표는 다음과 같다.

노드	1	2	3	4	5	6
거리	0	2	4	1	2	INF

노드 4를 통해 갈 경우에 대해 모두 검색 했으므로, 노드 4에 대한 탐색은 하지 않아도 된다.

이 경우 1과 가장 가까운 노드는 2와 5이다. 

위와 같은 방법을 2와 5에 대해 모두 적용 하는 방식을 통해 node 1에서 각 node까지의 최소 거리를 탐색 할 수 있다.

 

일반 list를 사용할 경우, 2중 for문을 사용하게 되고, 시간복잡도는 O(N^2)이다.

이때 heap을 사용할 경우, 가장 거리가 짧은 노드를 top에 위치 시켜 시간 복잡도를 줄일 수 있다.

heap을 사용할 경우 O(Nlog(N))으로 구현이 가능하다.

 

<소스코드>

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
int num = 6; // 노드 갯수
int INF = INT_MAX;
int dis[7]; // 최소 거리
vector<pair<int,int>> v[7]; // 간선 정보
 
void dijkstra(int start){
    priority_queue<pair<int,int>> pq; // 거리, 노드
    dis[start] = 0;
    pq.push(make_pair(0, start));
    
    while(!pq.empty()){
        
        int cur = pq.top().second; // 현제 노드
        int dist = pq.top().first * -1; // 거리 (first 에는 음수가 들어가 있으므로)
        pq.pop();
        
        // 이미 담겨있는것 보다 거리가 멀면 넘어감. -> 이부분을 통해 중복 제외 처리
        if(dis[cur] < dist) continue;
        
        for(int i = 0; i<v[cur].size(); i++){
            int next = v[cur][i].first;
            int nxt_dis = v[cur][i].second + dist;
            
            if(nxt_dis < dis[next]){
                dis[next] = nxt_dis;
                pq.push(make_pair(nxt_dis * -1, next));
            }
        }
    }
}
 
int main() {
    
    for(int i = 1; i<7; i++){
        dis[i] = INF;
    }
    
    // 노드-간선 데이터
    // 노드 / 연결노드 / 거리
    v[1].push_back(make_pair(2,2));
    v[1].push_back(make_pair(4,1));
    v[1].push_back(make_pair(3, 5));
 
    v[2].push_back(make_pair(1, 2));
    v[2].push_back(make_pair(4, 2));
    v[2].push_back(make_pair(3, 3));
 
    v[3].push_back(make_pair(1, 5));
    v[3].push_back(make_pair(2, 3));
    v[3].push_back(make_pair(4, 3));
    v[3].push_back(make_pair(5, 1));
    v[3].push_back(make_pair(6, 5));
 
    v[4].push_back(make_pair(1, 1));
    v[4].push_back(make_pair(2, 2));
    v[4].push_back(make_pair(3, 3));
    v[4].push_back(make_pair(5, 1));
 
    v[5].push_back(make_pair(3, 1));
    v[5].push_back(make_pair(4, 1));
    v[5].push_back(make_pair(6, 2));
 
    v[6].push_back(make_pair(3, 5));
    v[6].push_back(make_pair(5, 2));
 
    dijkstra(1);
 
    for(int i = 1; i<7; i++){
        cout << "TO " << i << " : " << dis[i] << endl;
    }
}