[개념 정리] 최소 거리 구하기: 다익스트라 (개념 및 C++ 우선순위 큐를 이용한 구현)

다익스트라 알고리즘 개념

다익스트라 알고리즘 또는 데이크스트라 알고리즘은 그래프에서 노드(Node) 간의 최단 경로를 찾는 알고리즘 중 하나로, 시작 노드(Node)가 주어졌을 때 해당 시작점으로부터 다른 모든 노드(Node)까지의 최단 경로 찾습니다. 해당 알고리즘은 도로 교통망 및 라우팅 프로토콜 등에서 많이 활용되고 있습니다. 예를 들어, 그래프의 꼭짓점들이 각각 도시를 나타내고, 변들이 도시 사이를 연결하는 도로의 길이를 나타낸다면, 다익스트라 알고리즘을 통하여 두 도시 사이의 최단 경로를 찾을 수 있습니다.

다익스트라 동작

소스(Source)는 시작 노드(Node)이며, dist[]를 시작 노드(Node)와 시작 노드(Node)를 포함한 모든 노드까지의 거리로 정의합니다. dist[]에서는 시작 노드(Node)를 포함하고 있기 때문에 시작 노드(Node) 간의 거리는 0으로 부여하고, 나머지 노드(Node)에 대한 거리는 무한대로 초기 값을 부여합니다. prev[]를 이전에 방문한 노드(Node)로 정의합니다.

다익스트라 알고리즘 슈도 코드(pseudocode), 출처: 위키피디아

슈도 코드를 보면 알 수 있듯이, Q에는 모든 노드(Node)를 저장하고 해당 Q안에 존재하는 노드(Node) 중 최소 거리를 갖는 노드(Node)를 다음 방문 노드(Node)로 설정합니다. 초기 상태에는 dist[]에서 시작 노드(Node)의 값만 0이고 나머지는 무한대를 가지므로 항상 시작 노드(Node)가 선택됩니다. 선택된 노드(Node)는 Q에서 제거되고, 해당 노드(Node)에 연결된 다른 노드(Node)들을 확인하며 현재 dist[]에 저장된 값보다 짧은 거리를 발견했을 때 dist[]와 prev[]의 값을 업데이트합니다. 

 

다익스트라 알고리즘 구현

1. 리스트 기반 구현 (Vanilla Code) 

#include <iostream>
#include <vector>
#include <limits.h>

using namespace std;

vector<bool> visited; // 방문 유무를 저장하는 벡터 선언
vector<int> d; // 시작 노드에서부터 각 노드까지의 최단 거리를 저장하는 벡터 선언

int getSmallestNode(int V) // 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환.
{
    int min_value=INT_MAX;
    int index = 0;
    
    for(int i=0; i<V; i++)
    {
        if(d[i] < min_value && !visited[i])
        {
            min_value = d[i];
            index = i;
        }
    }
    
    return index;
}

void dijkstra(int V, vector<pair<int,int>> graph[], int start)
{
    d[start]=0;
    visited[start]= true;
    
    for(int j=0; j<graph[start].size(); j++)
    {
        int adj = graph[start][j].first;
        d[adj] = graph[start][j].second; // 최단거리 테이블에 초기값 세팅
    }
    
    for(int i=0; i<V-1; i++)
    {
        int now = getSmallestNode(V);
        visited[now]=true;
        
        for(int j=0; j<graph[now].size(); j++)
        {
            int cost = d[now] + graph[now][j].second;
            if(cost<d[graph[now][j].first])
            {
                d[graph[now][j].first]=cost;  // 최단 거리 업데이트
            }
        }
    }
}

int main()
{
    int V, E, src;  // (V: # of nodes, E: # of edges, start: source)
    cin >> V >> E;  // 모든 간선 정보를 입력 받기 
    cin >> src;  // 시작점 입력 받기
    
    vector<pair<int,int>> graph[V];  // pair를 저장하는 벡터 V 개 생성 
    for (int i = 0; i < E; i++)
    {
        int from, to, cost;
        cin >> from >> to >> cost;  
        graph[from-1].push_back({to-1, cost});  // graph[] 에 from에서 to까지 가는 가는 비용 저장
    }
    
    d.assign(V, INT_MAX);  // 초기 값을 무한대로 저장
    visited.assign(V, 0);  // 방문한 적 없음을 선언
    
    dijkstra(V, graph, src-1);
    
    // 모든 노드로 가기 위한 최단 거리를 출력
    for (int i = 0; i < V; i++)
    {
        if (d[i] == INT_MAX)
            cout << "INFINITY ";
        else
            cout << d[i] << " ";
    }
    return 0;
}

노드(Node)의 수와 간선(Edge)의 수를 먼저 받고, 시작 노드(Node) 및 연결 관계정보를 받는다면, 시작 노드(Node)로 부터 다른 모든 노드(Node)까지 최소 거리를 출력할 수 있습니다. graph[]는 사이즈가 V인 벡터의 array로 graph[v-1]는 V개의 노드(Node) 중 v번 째에 연결되어 있는 다른 노드의 (번호 -1)와 거리를 저장합니다. -1을 하는 이유는 인덱스가 0부터 시작하기 때문입니다. 다익스트라 함수의 내부는 시작점이 주어졌기 때문에, 해당 노드(Node) 방문했음을 visited[]에 저장하고, 해당 노드(Node)에 연결된 정보를 graph에서 찾아 d[]의 값을 업데이트해준다. 그 후, 앞에서 설명했듯이, d[]에 저장된 값 중 가장 짧은 거리를 찾아 다음으로 갈 노드(Node)로 선정합니다. 이 때, 이미 다녀온 노드(Node)에는 방문할 필요가 없으니, 제외합니다. 거리 기준으로 다음으로 방문할 노드(Node)가 선정되면, 해당 노드(Node)에 연결된 모든 노드(Node)를 확인하여 현재까지 저장된 거리보다 짧은 거리를 발견했을 경우 d[]를 업데이트합니다. 모든 노드(Node)를 확인하면 다시 d[]에서 거리를 확인하여 다음으로 방문할 노드(Node)를 찾고, 이를 모든 Node를 방문할 수 있을 때까지 반복합니다. 해당 코드는 단순하게 구현했을 때, d[]를 확인하여 가장 짧은 노드(Node)를 찾고 이를 노드(Node) 개수만큼 반복하므로 실행시간은 O(V2)에 비례한다.

 

2. 우선 순위 Queue를 활용한 구현

#include <bits/stdc++.h>

using namespace std;

vector<bool> visited; // 방문 유무를 저장하는 벡터 선언
vector<int> d; // 시작 노드에서부터 각 노드까지의 최단 거리를 저장하는 벡터 선언

void dijkstra(int V, vector<pair<int,int>> graph[], int start)
{
    priority_queue<pair<int,int>>pq; // (거리, 노드 인덱스)를 거리 순서대로 정렬할 queue 생성
    
    pq.push({0,start}); //시작 노드로 가기위한 최단 경로는 0으로 설정하여, 큐에 삽입.
    d[start]=0;
    
    while(!pq.empty())
    {
        int dist = -pq.top().first; //현재 노드까지의 비용
        int now = pq.top().second; // 현재 노드
        pq.pop();
        
        if(d[now]<dist) // 이미 최단경로를 체크한 노드인 경우 패스
            continue;
        
        for(int i=0; i<graph[now].size(); i++)
        {
            int cost = dist+graph[now][i].second; // 거쳐서 가는 노드의 비용을 계산
                                                  // 현재노드까지 비용 + 다음 노드 비용
            if(cost<d[graph[now][i].first]) // 비용이 더 작다면 최단경로 테이블 값을 갱신.
            {
                d[graph[now][i].first]=cost;
                pq.push(make_pair(-cost,graph[now][i].first));
            }
        }
    }
}

int main()
{
    int V, E, src;  // (V: # of nodes, E: # of edges, start: source)
    cin >> V >> E;  // 모든 간선 정보를 입력 받기 
    cin >> src;  // 시작점 입력 받기
    
    vector<pair<int,int>> graph[V];  // pair를 저장하는 벡터 V 개 생성 
    for (int i = 0; i < E; i++)
    {
        int from, to, cost;
        cin >> from >> to >> cost;  
        graph[from-1].push_back({to-1, cost});  // graph[] 에 from에서 to까지 가는 가는 비용 저장
    }
    
    d.assign(V, INT_MAX);  // 초기 값을 무한대로 저장
    visited.assign(V, 0);  // 방문한 적 없음을 선언
    
    dijkstra(V, graph, src-1);
    
    // 모든 노드로 가기 위한 최단 거리를 출력
    for (int i = 0; i < V; i++)
    {
        if (d[i] == INT_MAX)
            cout << "INFINITY ";
        else
            cout << d[i] << " ";
    }
    return 0;
}

 

리스트 기반으로 작성했을 때 가장 짧은 거리를 찾기 위해 반복문을 도는 부분을 priority queue는 자동으로 처리해주어 해당 부분을 작성할 필요가 없다. 또한 반복문을 돌 경우 O(n)의 시간 복잡도를 가지지만, priority queue 내부에서 자동으로 처리해주는 정렬은 O(log(n))의 시간 복잡도를 가진다.

주의할 점은 우선 순위의 큐는 default는 내림차순이기 때문에 가장 큰 값이 front에 위치하게 된다. 가장 작은 값이 앞에 두기 위해서 큐에 '-'를 곱하여 음수로 넣고 다시 꺼낼 때 '-'를 다시 곱해서 본래의 값을 사용한다. '-'를 곱하면 가장 큰 값이 가장 작은 값이 되고 가장 작은 값이 가장 큰 값이 되기 때문이다. 

또는 priority_queue<pair<int,int> ,vector<pair<int,int> >,greater<pair<int,int> > pq로 선언하시면 오름차순으로 명시해주었기 때문에 가장 작은 값이 가장 위로 정렬된다.