다익스트라 알고리즘(Dijkstra's algorithm)

 다익스트라 알고리즘(Dijkstra's algorithm)은 Weighted graph, 즉 간선에 가중치가 있는 그래프가 주어졌을 때, 하나의 고정된 특정 노드에서 시작해 다른 모든 노드로 가는 최단 경로를 찾는 알고리즘이다. 

 

 벨만-포드 알고리즘도 Weighted graph의 Shortest path를 찾을 때 사용될 수 있지만, 다익스트라 알고리즘이 좀 더 효율적이기 때문에 더 자주 사용된다(O(E V) vs O(E log V)).

그러나 다익스트라 알고리즘은 가중치가 음수인 간선이 존재하는 경우에는 사용할 수 없고, 이러한 경우에는 벨만-포드 알고리즘을 사용해야한다.

 

 다익스트라 알고리즘은 시작 노드에서 모든 다른 노드까지의 거리를 저장하고, 탐색 과정에서 값을 줄여나가는 방식으로 최단 경로를 찾는다.

1. 시작 노드까지의 거리는 0, 다른 모든 노드까지의 거리는 무한대로 초기화한다.

2. 아직 거리를 줄이지 않은 노드 중, 시작 노드로부터 거리가 가장 가까운 노드를 고른다.

3. 선택된 노드에서 다른 노드로 연결된 간선의 가중치를 확인하고, 노드까지의 거리를 줄일 수 있다면 줄인다.

4. 위 과정을 모든 노드가 처리될 때까지 반복한다.

 

 가중치가 음수인 간선이 존재하지 않기 때문에, 모든 간선은 최대 한 번씩만 처리된다.

(가중치가 항상 양수이기 때문에 간선을 처리할수록 항상 거리가 늘어나게 된다. 따라서 모든 간선을 한 번씩 처리한 경우가 최악의 경우가 되고 어떤 간선도 두 번 이상 처리되지 않는다.)

 

[ 구현 ]

 다익스트라 알고리즘을 구현하기 위해

1. 그래프를 인접 리스트로 표현하기 위한 adjList 2차원 배열

  - adjList[u]는 {v, w}를 저장한다.

  - 노드 u에서 v로 향하는 가중치 w의 간선이 있음을 의미한다.

 

2. 시작 노드 s에서 다른 모든 노드까지의 거리를 저장할 dist 배열

  - dist[x]는 시작 노드에서 x까지의 거리를 의미한다.

  - 시작 노드를 s로 정의했을 때, dist[s] = 0을 제외한 모든 dist[x]는 INF 값으로 초기화한다.

 

3. 방문한 노드를 체크하기 위한 visited 배열

  - 이미 방문한 노드일 경우, 간선으로 연결된 v노드의 dist[v]에 이미 최소 거리가 저장되었을 것이다.

  - 따라서 방문했던 노드를 중복 처리하지 않기 위해, 노드를 방문했는지 저장하는 visited 배열이 필요하다.

 

4. 시작 노드와 거리가 가까운 노드 순서대로 저장하고 처리하기 위한 우선순위 큐가 필요하다.

  - 시작 노드와 거리가 가까운 순서대로 노드를 처리하기 위해 필요하다.

  - {-w, u}의 형태의 값이 우선순위 큐에 담기게 된다.

    - C++의 priority_queue는 최대힙이기 때문에 가중치를 음수로 만들어 저장해야 한다(최소힙처럼 동작).

 

 위에서 설명한 배열과 우선순위 큐를 이용해 구현한 코드는 다음과 같다.

 

[ 구현 코드 ]

struct Dijkstra {
    
    int s;
    vector<vector<pair<int, int>>> adjList;
    vector<int> dist;
    vector<bool> visited;
    
    void init(vector<vector<pair<int, int>>>& edge, int source) {
        
        s = source;
        adjList = edge;
        dist.resize(adjList.size());
        visited.resize(adjList.size());

        for(int i = 0; i < dist.size(); i++) {
            if(i == source) {
                dist[i] = 0;
            } else {
                dist[i] = 1<<30; // INF
            }
        }
    }
    
    void dijkstra() {
        
        priority_queue<pair<int, int>> pq;
        pq.push({0, s});
        
        while (!pq.empty()) {
            int u = pq.top().second; // cur node
            pq.pop();
            
            if(visited[u]) continue;
            visited[u] = true;
            
            for(auto vw : adjList[u]) {
                int v = vw.first;
                int w = vw.second;
                
                if(dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.push({-dist[v], v});
                }
            }
        }
    }
};

 우선순위 큐에 노드를 삽입할 때 시간복잡도는 O(log V)이고, 노드 삽입은 최악의 경우라도 모든 간선에 대해 한 번씩만 처리되기 때문에 위 방법으로 구현한 다익스트라 알고리즘의 시간복잡도는 O(E og V)가 된다.

 

구현한 구조체를 이용한 최단 경로 문제 풀이

[ BOJ - 1753번 ] 최단 경로 (C++)

 

[ 참고 자료 ]

안티 라크소넨 , ⌜알고리즘 트레이닝 2판 - 프로그래밍 대회 입문 가이드⌟, 인사이트, 2022, 110~113쪽