다익스트라 알고리즘이란?

코테에 쓰이는 개념은 많은데 자주 까먹고 다시 찾는 일이 많아 하나씩 블로그에 정리해보기로 했다. 처음으로 정리할 다익스트라 알고리즘은 한 노드에서 다른 노드까지의 최단 경로를 찾는데 쓰이는 알고리즘이다. 그 진행과정은 다음과 같다.

노드의 수 만큼의 크기를 가진 1차원 배열(이하 최단거리 테이블)을 만든다.
최단거리 테이블을 모두 큰 수(이하 inf)로 채운다.
출발 노드를 선택하고 최단 거리 테이블의 출발노드 부분을 0으로 한다.
현재 노드에 인접한 노드들의 최단거리 테이블을 갱신한다.
현재 노드에 인접한 노드 중 방문하지 않은 노드이면서 가장 거리가 짧은 노드를 방문한다.
4~5번을 반복한다. 이 때 주의할 점은 새로 방문한 노드도 출발 노드와 이어진 하나의 노드로 본다는 것이다. 따라서 5번 과정을 할 때 현재와 출발노드 둘 다 보아야 한다.

설명이 좀 이해하기 힘들게 적히긴 했지만 아무튼 여기서 중요한 것은 지금까지 방문한 노드들 모두에서 인접한 노드 중 가장 짧은 거리의 노드를 찾아야한다는 것이다. 이 과정을 원활히 하기 위해 기능이 보통 사용된다. 우선순위 큐에 pair 기능을 활용하여 <거리, 노드>를 입력하면 거리를 기준으로 정렬되므로 가장 짧은 거리의 노드를 바로 찾을 수 있기 때문이다. 우선순위 큐를 활용한 다익스트라 코드 예시는 아래와 같다.

#include <vector>
#include <queue>
#include <iostream>

using namespace std;

# define INF 1000000

// 시작 위치와 각 노드의 인접노드와 거리를 가진 graph 배열을 받아서
// 최소 거리 행렬을 반환함
vector<int> dijkstra(int start, int N, vector<pair<int, int>> graph[])
{
    vector<int> dist(N, INF);  // 거리를 저장할 최단 거리 리스트
    priority_queue<pair<int, int>> pq;  // 우선순위 큐

    dist[start] = 0;  // 시작노드는 0으로 초기화
    pq.push({ 0, start });  // 우선순위 큐에 push

    while (!pq.empty())
    {
        int cur_dist = -pq.top().first; // 현재 방문한 노드의 거리
        int cur_node = pq.top().second;  // 현재 방문한 노드의 인덱스
        pq.pop();

        for (int i = 0; i < graph[cur_node].size(); i++)
        {
            int nxt_node = graph[cur_node][i].first;  // 인접 노드의 인덱스
            int nxt_dist = cur_dist + graph[cur_node][i].second;  // 인접 노드까지의 거리

            if (nxt_dist < dist[nxt_node])  // 현재의 거리가 최단거리 테이블의 값보다 작다면
            {
                dist[nxt_node] = nxt_dist;  // 거리값 갱신
                pq.push({ -nxt_dist, nxt_node });  // 우선순위 큐에 push
            }
        }
    }

    return dist;  // 최단거리 테이블 리턴
}

int main()
{
    const int N; // 노드의 개수
    int E;  // 간선의 개수
    vector<pair<int, int>> graph[N];  // 노드간의 거리와 인덱스를 담을 배열

    for (int i = 0; i < E; i++)
    {
        int from, to, cost;  // 간선의 시작, 끝, 거리
        cin >> from >> to >> cost;
        graph[from].push_back({ to, cost });  // 무방향 그래프이므로 시작과 끝 둘 다 벡터에 넣어준다
        graph[to].push_back({ from, cost });
    }

    vector<int> dist = dijkstra(0, N, graph);
    
    cout << "끝점까지의 최단거리" << dist[N - 1] << endl;
    
    return 0;
}

향후 코테를 풀때마다 검색하지 말고 이렇게 참고할 자료를 하나 둘 만들어갈 예정이다.