다익스트라(Dijkstra) 최단 경로 알고리즘

다익스트라 알고리즘이란 무엇인가?

음의 가중치가 없는 그래프의 한 정점(V)에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘입니다.

기존에는 O(V^2)의 시간복잡도를 가졌으나, 시간이 지나 우선순위 큐를 이용하여 더욱 개선된 알고리즘이 생겨났으며 

O((V+E)logV)(V : 정점의 개수, E : 간선의 개수)의 시간 복잡도를 가질 수 있게 되었습니다.

O(VlogV)(각 노드마다 미방문 노드 중 출발점으로 현재까지 계산된 최단 거리를 가지는 노드를 찾는데 걸리는 시간) + O(ElogV) (각 노드마다 이웃한 노드의 최단거리를 갱신할 때 걸리는 시간)으로 보시면 될 것 같습니다.

출처 : https://namu.wiki/w/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

다익스트라 알고리즘 - 나무위키

다익스트라 알고리즘은 간선들 중에 가중치가 음수인 경우가 절대 있으면 안 되기 때문에 이 부분을 고려하여 알고리즘을 적용시켜야 합니다. 만약, 가중치의 합이 음수가 된다면, 벨만-포드 알고리즘을 사용해야 하는데 이 알고리즘은 추후 포스팅 하겠습니다.

 

다음과 같이, 각 지점은 노드(V)로 표현되고, 한 지점과 다른 지점을 연결하는 영역은 간선(E)으로 표현되는 것을 확인할 수 있습니다. 다익스트라는 한 지점에서 다른 지점(ex) 1번->3번, 2번->3번)으로 가는 최단 경로와 혹은 모든 이동 경로의 최소 비용을 구하는데 유용한 알고리즘입니다. 

또한, 매 상황에서 가장 비용이 적은 노드(최적화된 해)를 선택하여 값을 누적해야 하기 때문에 탐욕적인 원리를 적용하는 관점에서 그리디 알고리즘으로 분류됩니다.

 

동작 과정

1. 출발 노드 설정
2. 최단 거리 테이블 초기화
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택(O(VlogV))
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신(O(ElogV))
5. 위 과정 3, 4번 반복

 

1번 노드 기준으로 나머지는 아직 모르기 때문에 거리를 INF(무한)으로 초기화합니다.

1번 노드를 통해 인접 노드를 확인하여 최단 거리가 가장 짧은 값으로 초기화해줍니다.

1번 노드에서 최단 거리가 가장 짧은 노드가 4번이기 때문에 4번 노드에 관련된 노드를 처리해 줍니다. 다음과 같이 3번 노드의 값도 1->3으로 가는 것(5)보다 1->4->3(1+3)으로 가는 것이 더 가깝기 때문에 값을 4로 갱신해주었습니다. 이러한 로직을 지속적으로 반복해 줘서 최적해를 구할 수 있게 됩니다.

 

단계를 거치면서 한 번 처리된 노드의 최단 거리는 고정되기 때문에 더 이상 바뀌지 않습니다.

• 한 단계당 하나의 노드에 대한 최단 거리를 확실하게 찾는 것으로 해석해야 합니다.

다익스트라 알고리즘을 수행한 뒤에 테이블에 각 노드까지의 최단 거리 정보가 저장됩니다.

• 완벽한 형태의 최단 경로를 구하기 위해서는 소스코드에 추가적인 기능을 더 넣어야 합니다.

<코드, 노드의 개수가 5000개 이하인 경우(최단 거리가 가장 짧은 노드를 선형 탐색)>

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define INF 2e9

using namespace std;

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

vector<pair<int, int>> graph[100001];
// 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
bool visited[100001];
// 최단 거리 테이블 만들기
int d[100001];
// 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환
int getResult() 
{
    int min_value = INF;
    int now = 0;
    for(int i=1;i<=N;i++)
    {
        if(d[i]<min_value && !visited[i]) 
        {
            min_value = d[i];
            now = i;
        }
    }
    return now;
}
void dijkstra(int start)
{
    d[start] = 0;
    //시작 노드 초기화
    visited[start] = true;
    for(int j=0;j<graph[start].size();j++)
    {
        d[graph[start][j].first] = graph[start][j].second;
    }
    // 시작 노드를 제외한 전체 N - 1개의 노드에 대해 반복
    for(int i=0;i<N-1;i++)
    {
        int now = getResult();
        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,cost;
        cin>>a>>b>>cost;
        graph[a].push_back({b,cost});
    }
    
    //최단 거리 테이블을 모두 무한으로 초기화
    memset(d,INF,sizeof(d));
    
    //다익스트라 알고리즘 수행
    dijkstra(Start);

    //모든 노드로 가기 위한 최단 거리를 출력
    for(int i=1;i<=N;i++)
    {
        if(d[i]==INF) {
            cout<<"INFINITY"<<'\n';
        }
        //도달할 수 없는 경우
        else {
            cout<<d[i]<<'\n';
        }
    }
    

}

<코드, 노드의 개수가 10000개가 넘는 경우>

우선순위 큐(Priority Queue) 활용

우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조입니다.

우선순위 큐를 구현하기 위한 자료구조 중에서 최대힙과 최소힙이 있는데, 이 문제에서는 최소 힙을 적용하면 됩니다.

또한 이를 적용하면 시간 복잡도도 삽입과 삭제 연산에서 O(logN)으로 최소화할 수 있게 됩니다. 

 

<같은 유형의 문제>

https://www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

<코드>

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
#define INF 2e9

using namespace std;

// 노드의 개수(N), 간선의 개수(M), 시작 노드 번호(Start)
// 노드의 개수는 최대 100,000개로 가정
int N, M, Start, End;

vector<pair<int, int>> graph[100001];
// 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
bool visited[100001];
// 최단 거리 테이블 만들기
int d[100001];
// 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환
int getResult() 
{
    int min_value = INF;
    int now = 0;
    for(int i=1;i<=N;i++)
    {
        if(d[i]<min_value && !visited[i]) 
        {
            min_value = d[i];
            now = i;
        }
    }
    return now;
}
void dijkstra(int start)
{

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>> pq;
    pq.push({0, Start});
    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({ cost,graph[now][i].first});
            }
        }
    }
}
int main()
{
    cin>>N>>M;

    //모든 간선 정보 입력 받기
    for(int i=0;i<M;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        graph[a].push_back({b,c});
    }

    cin>>Start>>End;
    //최단 거리 테이블을 모두 무한으로 초기화
    fill(d,d + 100001,INF);
    
    //다익스트라 알고리즘 수행
    dijkstra(Start);

    cout<<d[End]<<'\n';
    

}

<참고 자료>

https://www.youtube.com/watch?v=acqm9mM1P6o