[최단경로] 다익스트라(Dijstra) 알고리즘

30. 최단 경로 알고리즘

BFS와 구현방법이 상당히 비슷하다.

다익스트라 알고리즘

다익스트라(Dijstra, 데이크스트라) 알고리즘은 다음과 같다.

d[v]는 시작점 s로 부터 그래프의 모든 점까지의 최단거리이다.

아이디어는 BFS와 비슷한데,

가중치가 붙어있는 그래프를 다루므로, queue에 넣을 때는 (지금까지 누적 cost, 다음점)을 넣어준다.

매번 while문의 처음에서 cost가 최소인 점을 선택하는 이유는, 최단 거리가 되는 가능성이 있는 점들을 먼저 탐색하고 d[v]를 기록해주기 위함이다.

이렇게 해서 S 안에 다른 원소가 뽑혀 이미 기록된 d[v] 과 비교하여 더 크다면, 무시해주면 된다!

그래프를 직접 그려보면서, 알고리즘을 이해하는 것이 효율적인 것 같다.

이렇게 해서 직접 코드를 구현할 때는, 최소인 점을 찾기위해서 priority queue를 구현한다.

#include <cstdio>
#include <vector>
#include <queue>
#include <utility>

#define INF 0x7fffffff
#define MAX_V 100
using namespace std;

int V, E;
vector<pair<int, int> > adj[MAX_V];

vector<int> dijstra(int src){
    vector<int> d(V, INF);
    d[src] = 0;

    priority_queue<pair<int, int> > pq;
    pq.push({0, src});
    while(!pq.empty()){
        int cost = -pq.top().first;
        int v = pq.top().second;
        if (d[v] < cost) continue;

        for (int i=0; i<adj[v].size(); ++i){
            int w = adj[v][i].first;
            int nextDist = cost + adj[v][i].second;
            if (d[w] > nextDist){
                d[w] = nextDist;
                pq.push({-nextDist, w});
            }
        }
    }
}

priotiry_queue는 기본값으로 최댓값이 top이 되도록 정렬을 하므로, 최솟값을 뽑고 싶다면, -를 붙여서 삽입해주면 된다.

물론, 최솟값이 되도록 정렬하게 만들 수도 있지만, 코드를 짧게 쓰고 싶다면 위와 같은 방법을 추천한다.

시간복잡도

1) 다익스트라는 모든 간선을 검사합니다 따라서 O(|E|),

2) 다음으로 우선순위 큐에 원소를 넣고, 삭제하는 데 드는 총 시간을 따져봅시다.

우선순위 큐에 들어갈 수 있는 최대 점의 수는 O(|E|)입니다. (모든 간선이 검사될 때마다 최대로 한 번 들어갈 수 있습니다.) 여기에 추가 또는 삭제하는 시간은 O(log|E|)이므로, 전체 시간복잡도는 O(ElogE)입니다.

따라서 총 시간복잡도는 O(|E| + |E|log|E|) = O(|E|log|E|)이고,

보통 |E| <= |V|² 이므로, O(|E|log|V|)라고 볼 수도 있습니다.

다익스트라 2

정점의 수가 적거나 간선의 수가 매우 많은 경우에는 우선순위 큐를 사용하지 않고 구현하는 방식이 더 빠를 수 있습니다.

각 정점을 방문했는지 여부를 나타내는 배열 visited[]를 사용합니다.

bool visited[MAX_V];
vector<int> dijstra2(int src){    
    vector<int> d(V, INF);
    d[src] = 0;
    // visited[src] = true;
    while(true){
        // Find the closest, not visited vertex
        int closest = INF;
        int v;
        for (int i=0; i<V; ++i){
            if (d[i] < closest && !visited[i]){
                v = i;
                closest = d[i];
            }
        }
        if (closest == INF) break;

        // Visit the closest vertex (v → w)
        visited[v] = true;
        for (int i=0; i<adj[v].size(); ++i){
            int w = adj[v][i].first;
            if (!visited[w]){
                d[w] = min(d[w], d[v] + adj[v][i].second);
            }
        }
    }
}

시간복잡도는 O(|V|² +|E|) 입니다.