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

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

그래프 상에서 최단 경로(최소 비용)를 찾는 알고리즘 중 하나이다. 그 중 특히, 시작 노드와 도착 노드가 주어졌을 때 두 노드 사이의 최단 경로를 찾을 때 유용하다. 또한 벨만-포드 알고리즘이 음수 간선이 있어도 사용 가능한 데 비해, 다익스트라는 양수의 가중치 값을 갖는 간선에 대해서만 사용할 수 있다!

 

만약 음수의 가중치값을 가지는 간선이 존재한다면 다익스트라 알고리즘을 이용할 수 없다. 그 이유는 다익스트라 알고리즘의 경우 그리디 알고리즘을 적용하여 현재 방문 정점과 연결된 정점들 중 가장 적은 가중치값을 가지는 정점을 선택해가며 값을 갱신해준다. 그 후에는 방문한 정점에 대해서는 건드리지 않는다. 

a ---(3) b, a ---(5) c, b ---(x) c 와 같은 그래프가 존재한다고 가정해보자. 다익스트라 알고리즘에서 a를 시작정점으로 한다면 인접 정점 중 가중치값이 가장 작은 b(3<5)를 선택해 방문할 것이다. 그 이후에는 a에서 b로 이동하는 최소 비용이 3이라고 단정짓고 다시는 b를 방문하지 않게 될 것이다.

하지만 만약 x의 값이 음수라면? 5 + x < 3, 즉 x < -2 보다 작은 음수라면 위와 같은 가정이 깨진다. 반대로 x가 무조건 양수라면 5 + x < 3를 만족시키는 값은 있을 수 없고, 우리는 a에서 b로 이동하는 최소 비용이 3이라고 확정지을 수 있다. 이때문에 다익스트라 알고리즘에서는 모든 간선 가중치가 양수여야 한다!

2. 진행 과정 

다익스트라 알고리즘의 진행 과정은 다음과 같다.

1. 방문하지 않은 정점 중 가장 가중치 값이 작은 정점을 시작 정점으로 하여 방문 체크 해준다.

2. 해당 정점의 인접 정점들에 대해 거리를 최소값으로 갱신해준다.

3. 방문한 정점의 인접 정점들에 대해 비용이 가장 적게 드는 정점을 선택하여 방문해준다. 2-3 번 과정을 반복한다. 

 

 

- 시작 정점을 0이라고 하자. 모든 거리 배열은 INF로 초기화 해준다.

 

 

- 시작 정점을 방문한다. (방문한 정점은 주황색으로 표시됨.)

- 시작 정점의 인접 정점 1, 2, 3번 정점에 대해서 거리를 갱신해준다.

 

 - 방문한 정점과 연결되어 있는 정점들 중, 방문하지 않은 상태이고 가장 적은 비용이 드는 2번 정점을 선택해 방문한다.

- 2번 정점을 통해 연결되어 있는 정점들의 거리를 갱신해준다.

 

- 방문한 2번 정점과 연결되어있는 정점들 중, 방문하지 않고, 가장 가중치가 작은 3번 정점을 선택해 방문해 준다.

- 3번 정점을 통해 연결되어 있는 정점들의 거리를 갱신해준다.

 

- 방문한 3번 정점과 연결되어있는 정점들 중, 방문하지 않고, 가장 가중치가 작은 4번 정점을 선택해 방문해 준다.

- 4번 정점을 통해 연결되어 있는 정점들의 거리를 갱신해준다. 여기서는 갱신할 거리가 없다.

 

- 마지막으로 방문하지 않았고, 가장 가중치가 작은 1번 정점을 방문한다.

- 1번 정점을 통해 연결되어 있는 정점들의 거리를 갱신해준다. 여기서는 갱신할 거리가 없다.

- 모든 정점을 방문했으므로 종료한다.

 

위와 같은 과정을 거치면 최종적으로 dist 배열에 시작 정점인 0번 정점부터 각 정점까지의 최단 경로가 기록된다.

 

---

3. 구현 (c++)

다익스트라의 구현에는 배열을 이용하는 방법(O(V^2)의 시간복잡도)과 힙을 이용하는 방법(O(ElogV)의 시간복잡도)이 있다.

힙은 우선순위 큐를 이용해 구현 가능하며, 배열을 이용하는 것보다 더 빠르기 때문에 힙을 이용한 구현 방법으로 정리하도록 하겠다.

 

void dijkstra(int s){
    priority_queue<pair<int, int>> pq;

    dist[s] = 0;
    pq.push({0, s}); //cost, vertex

    while(!pq.empty()){
        int cost = -pq.top().first;
        int curr = pq.top().second;
        pq.pop();

        if(dist[curr] < cost) continue;

        for(int i=0; i<node[curr].size(); i++){
            int c = cost + node[curr][i].second;
            if(c < dist[node[curr][i].first]){
                dist[node[curr][i].first] = c;
                pq.push({-c, node[curr][i].first});
            }
        }
    }
}

 

- 우선순위 큐는 기본적으로 내림차순으로 반환하기 때문에 cost 값이 가장 작은 것부터 반환하도록 하기 위해 음수로 바꿔서 pq에 넣어줘야 한다.