C++ 우선순위 큐를 이용한 다익스트라 알고리즘 구현

이 글은 나동빈 님의 '이것이 취업을 위한 코딩테스트다' 책을 보고 정리한 내용입니다.

 

https://book.naver.com/bookdb/book_detail.nhn?bid=16439154

이것이 취업을 위한 코딩 테스트다 with 파이썬

 

우선 다익스트라 알고리즘의 기본 개념에 대해 정리한 글 이다.

https://hub1234.tistory.com/32

다익스트라 알고리즘(최단 경로 알고리즘 )기본 개념 원리

 

[C++] 우선순위 큐를 이용한 다익스트라 알고리즘 구현(최단 경로 알고리즘) 

다익스트라 알고리즘을 구현하는 방법은 두 가지가 있다.

1. 구현하기 쉽지만 느리게 동작하는 코드(리스트 기반)

2. 구현하기에 조금 더 까다롭지만 빠르게 동작하는 코드(우선순위 큐 기반)

이 두 가지를 모두 알아보겠다.

 

방법 1. 간단한 다익스트라 알고리즘 (리스트 기반)

간단한 다익스트라 알고리즘은 O(V^2)의 시간 복잡도를 가진다. V는 노드의 개수를 의미한다.

처음에 각 노드에 대한 최단거리를 담는 1차원 리스트를 선언한다.

이후에 단계마다 '방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택'하기 위해 매 단계마다 1차원 리스트의 모든 원소를 확인(순차 탐색)한다.

총 노드의 개수 V 만큼 진행을 하고 매 단계마다 모든 노드를 탐색하여 최단 거리가 가장 짧은 노드를 찾아야 하기에 V만큼 시간이 든다. 

고로 시간복잡도 O(V^2). 

노드의 개수가 10,000개를 넘어가는 경우라면 느리게 동작할 수 있다.

노드의 개수 및 간선의 개수가 많을 때는 이어서 설명할 우선순위 큐를 이용한 '개선된 다익스트라 알고리즘'을 이용해야 한다.

#include<iostream>
#include<vector>
using namespace std;
#define INF 1e9 // 무한을 의미하는 값으로 10억을 설정

// 노드의 개수(N), 간선의 개수(M), 시작 노드 번호(Start)
// 노드의 개수는 최대 100,000개라고 가정
int n, m, start;

vector<pair<int, int> > graph[100001]; // 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열

bool visited[100001]; // 방문한 적이 있는지 체크하는 목적의 배열 만들기

int d[100001]; // 최단 거리 테이블 만들기

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

void dijkstra(int start)
{
    d[start]=0;
    visited[start]= true;
    
    for(int j=0; j<graph[start].size(); j++)
    {
        int adjindex = graph[start][j].first;
        d[adjindex] = graph[start][j].second; // 최단거리 테이블에 초기값 세팅
    }
    
    for(int i=0; i<n-1; i++)
    {
        int now = getSmallestNode();
        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()
{
    cin >> n >> m >> start;
    // 모든 간선 정보를 입력받기
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;  // a번 노드에서 b번 노드로 가는 비용이 c라는 의미
        graph[a].push_back({b, c});
    }
    
    // 최단 거리 테이블을 모두 무한으로 초기화
    fill_n(d, 100001, INF);
    
    dijkstra(start);
    
    // 모든 노드로 가기 위한 최단 거리를 출력
    for (int i = 1; i <= n; i++)
    {
        // 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
        if (d[i] == INF)
        {
            cout << "INFINITY" << '\n';
        }
        // 도달할 수 있는 경우 거리를 출력
        else
        {
            cout << d[i] << '\n';
        }
    }
    return 0;
}

 

방법 2. 우선순위 큐를 이용한 다익스트라 알고리즘

다익스트라 알고리즘을 간단히 구현하면 시간 복잡도가 O(V^2)이다.

하지만 지금 배울 구현 방법을 이용하면 다익스트라 최단 경로 문제를 최악의 경우에도 시간 복잡도 O(ElogV)를 보장하여 해결할 수 있다.

V는 노드 개수 E는 간선 개수이다.

이전 알고리즘은 최단 거리가 가장 짧은 노드를 찾기 위해 모든 원소를 선형 탐색을 해야 했는데 이 부분을 힙(Heap) 자료구조를 이용해 빠르게 작동하도록 만들었다.

힙 자료구조를 이용하게 되면 특정 노드까지의 최단 거리에 대한 정보를 힙에 담아서 처리하므로 출발 노드로부터 가장 거리가 짧은 노드를 더욱 빠르게 찾을 수 있다. 이 과정에서는 선형 시간이 아닌 로그 시간이 걸린다. 

우선순위 큐를 적용하는데 알고리즘이 동작하는 기본원리는 동일하다.

최단 거리를 저장하기 위한 1차원 리스트(최단 거리 테이블)는 아까와 같이 그대로 이용하고,

현재 가장 가까운 노드를 저장하기 위한 목적으로만 우선순위 큐를 추가로 이용한다.

 

앞의 코드와 비교하였을 때 get_smallest_node() 라는 함수를 작성할 필요가 없다. 

최단 거리가 가장 짧은 노드를 선택하는 과정을 우선순위 큐를 이용하는 방식으로 대체하였기에 그 만큼 알고리즘 속도가 개선되었다.

#include <stdio.h>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
#define INF 1e9 // 무한을 의미하는 값으로 10억을 설정

// 노드의 개수(N), 간선의 개수(M), 시작 노드 번호(Start)
// 노드의 개수는 최대 100,000개라고 가정
int n, m, start;

vector<pair<int, int> > graph[100001]; // 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
int d[100001]; // 최단 거리 테이블 만들기

void dijkstra(int start)
{
    priority_queue<pair<int,int>>pq; // 거리, 노드 인덱스
    
    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(void)
{
    cin >> n >> m >> start;
    
    // 모든 간선 정보를 입력받기
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        // a번 노드에서 b번 노드로 가는 비용이 c라는 의미
        graph[a].push_back({b, c});
    }
    
    // 최단 거리 테이블을 모두 무한으로 초기화
    fill(d, d + 100001, INF);
    
    // 다익스트라 알고리즘을 수행
    dijkstra(start);
    
    // 모든 노드로 가기 위한 최단 거리를 출력
    for (int i = 1; i <= n; i++)
    {
        // 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
        if (d[i] == INF) {
            cout << "INFINITY" << '\n';
        }
        // 도달할 수 있는 경우 거리를 출력
        else {
            cout << d[i] << '\n';
        }
    }
}