길찾기 알고리즘(2) - 다익스트라 알고리즘

다익스트라 알고리즘

 

 다익스트라 알고리즘은 최단거리를 구하는 알고리즘중 가장 대표적인 알고리즘으로 아래와 같은 조건에서 사용하면 좋습니다.

 

- 간선간 음의 가중치가 없을때

- 시작지점이 한개의 정점으로 정해졌을 때 (시작점이 여러개라면 다익스트라를 여러번 돌려 해결이 가능합니다)

 

 다익스트라 알고리즘은 '가장 빠른 길'을 찾는 알고리즘으로 간선간 음의 값을 가지는 길은 없다고 생각합니다. 또한 플로이드-와샬보다 속도는 빠르지만 시작지점 1개에 대해서만 빠른 길을 찾는 알고리즘입니다.

 

 

 

조금 풀어쓴 다익스트라 알고리즘

예시 다익스트라 경로

 

1. 시작점 start, 도착점 finish, 각 경로와 가중치가 주어지게 됩니다.

 - 입력을 전부 받아오면 다익스트라를 위한 배열을 아래 표처럼 INF로 초기화해줍니다.

1	2	3	4	5
INF	INF	INF	INF	INF

 

 

2. 시작점에서 시작점으로 가는 비용은 0이니 시작 지점을 0으로 지정해 줍니다.

1	2	3	4	5
0	INF	INF	INF	INF

 - 이후 큐에 시작 지점을 넣어준 뒤 경로 탐색을 시작합니다.

 

 

3. 큐에서 원소를 하나 빼내고 경로가 담긴 배열과 비교해 배열을 업데이트 해줍니다.

1	2	3	4	5
0	3	2	INF	INF

 - 이후 이 지점들을 큐에 넣습니다.

 

 

4. 3번과 같은 과정으로 다음 지점인 2, 3 에서 갈 수 있는 값을 업데이트 해 줍니다. 이때는 2와 3까지 가는데 걸리는 비용을 반영해줘야 합니다.

1	2	3	4	5
0	3	2	5 (2+3)	10 (3+7)

 - 위 예시의 경우 [1 -> 2 -> 5]의 경로를 통해 5까지 가는 비용을 10이라고 해주고 4까지의 비용은 [1 -> 3 -> 4], 5로 업데이트 해 줍니다.

 - 이후 4, 5번 지점을 큐에 넣습니다.

 

 

5. 큐에 4, 5번이 있으니 4와 5에서 갈 수 있는 지점을 탐색합니다. 그런데 5는 갈 수 있는게 없어 작업을 하지 않고 4에서 출발하는 경로만 탐색하게 됩니다.

1	2	3	4	5
0	3	2	5	8

 - 여기서 [1 -> 2 -> 5]는 10의 비용이지만  [1 -> 3 -> 4 -> 5]가 8의 비용으로 더 빨리 갈 수 있으니 8로 업데이트 해 줍니다.

 - 더이상 경로가 없어 탐색은 중지합니다.

 - 결과로 나오는 위 배열이 시작지점 1에서 각 지점까지의 비용을 나타내 줍니다.

 

 

우선순위 큐?

 

 아래 코드를 보시면 우선순위 큐를 이용해서 문제를 풀이 했습니다. 우선순위 큐를 이용하게 되면 저장시 최소 비용이 top에 올 수 있게 만들 수 있어 기본 선형의 알고리즘보다 빠른 탐색이 가능합니다. 기존 선형탐색을 통해서 최소 거리를 구한다고 하면 시간복잡도가 O(N^2)이 나오지만 우선순위 큐에서는 O(NlogN)의 복잡도로 처리가 됩니다.

 (간선의 수를 E라고 하면 시간복잡도는 O(ElogN) 이 됩니다)

 

 

C++로 만든 간단한 코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// arr은 문제의 시작 지점이 인덱스로 가는데까지 비용을 저장
int arr[100];
// 입력에서 인덱스가 출발지가 되고 <도착지, 비용> 순으로 받아오게 됩니다.
vector<pair<int, int>> v[100];
void Djikstra(int start){
    // 큐에는 시간, 출발지 순으로 데이터가 들어가게 됩니다.
    // 때문에 우선순위 큐는 시간에 따라서 우선순위를 만들어 줍니다.
    priority_queue<pair<int, int>> q;

    arr[start] = 0;
    q.push(make_pair(0, start));

    while(!q.empty()){
        int cur = q.top().second;
        int time = -q.top().first;
        q.pop();

        if(time > arr[cur])
            continue;

        for(int i = 0; i < v[cur].size(); i++){
            int nextCur = v[cur][i].first;
            int nextTime = v[cur][i].second;

            if(arr[nextCur] > time + nextTime){
                arr[nextCur] = time + nextTime;
                q.push(make_pair(-arr[nextCur], nextCur));
            }
        }
    }
}

* 실제로 사용하는 경우 입력을 받은 뒤 비용을 저장하는 인덱스인 arr을 int의 최대값으로 초기화해야 합니다!

 

 위 코드에서 주의해야 할 점은 우선순위 큐에 값을 넣을때 마이너스(-)를 붙여서 넣는다는 것입니다. C++의 queue에 있는 priority_queue의 경우 '높은 값'이 top로 오게 됩니다. 그대로 사용한다면 꺼낼때 오히려 '제일 먼' 값을 고르게 되는 것이죠. 때문에 앞에 -를 붙여 우선순위 큐 안에 절댓값이 작은 값이 top로 오게 해주며 pop을 할 때 -를 붙여서 pop을 하면 문제 없이 사용이 가능합니다.

 

 또한 if(time > arr[cur]) 를 넣어서 속도에서 조금 더 이득을 볼 수 있게 했습니다.

 

 

다익스트라 알고리즘을 이용한 문제들

 

1. 백준 1753 (다익스트라)

 

1753번: 최단경로

가장 기본적인 문제로 다익스트라에 대한 개념만 잡고 간다면 무난히 풀 수 있는 문제입니다.

 

 

2. 백준 11779 (다익스트라 경로추적)

11779번: 최소비용 구하기 2

-풀이

백준 11779 최소비용 구하기 2 - C++, 다익스트라 경로추적

 기존 다익스트라에서 경로를 저장할 수 있어야 하며 간단하게 저장용 배열, 출력용 배열 1개씩 추가를 하면 풀이를 할 수 있습니다.

 

 

3. 백준 5719

5719번: 거의 최단 경로

-풀이

백준 5719 거의 최단 경로 - C++, 다익스트라, BFS

 아이디어는 금방 생각 나지만 첫 다익스트라를 한 후 경로를 어떻게 없앨지 고민을 해야 하는 문제입니다. 저같은 경우 BFS를 통해 경로를 역추적한 후 bool 배열을 하나 더 선언해 최단거리를 삭제할 수 있게 처리했습니다.