[알고리즘] 다익스트라 알고리즘

다익스트라를 써먹기 좋은 환경 예시

 

코테 준비를 하다보면 흔하게 등장해서 항상 공부해야지 하면서도 그러지 못했던 알고리즘들이 많이 생깁니다.

다익스트라 알고리즘도 그 중 하나인데요!

그래서 이번 기회에 확실하게 알고 넘어가야겠다 생각해서 공부했습니다 :)

 

목차

---

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

음의 가중치가 없는 경우에 특정 출발지에서 모든 정점까지의 최단거리를 구하는 알고리즘입니다.

 

대부분의 알고리즘은 최적의 해를 찾기 위해 등장하는데, 특정 상황에서 최적의 상황을 찾는 다익스트라 알고리즘은 현실 세계와도 굉장히 밀접하게 연관이 되어있기 때문에 정말 많이 쓴다고 볼 수 있습니다! (그래서 그런지 코테를 보면 심심치 않게 등장합니다!)

 

다익스트라의 동작 방식은 시작점을 잡고 최단거리를 갱신한 후에 가장 가까운 곳으로 이동해서 다시 그 곳에서 갈 수 있는 곳들을 확인하고 최단거리를 갱신하는 방식으로 진행됩니다.

 

쉽게 설명되어있는 영상들이 많아서 관련 영상을 확인해보시면 보다 쉽게 이해하실 수 있을 것이라고 생각합니다!

 

 

---

1. 알고리즘 코드짜기

이제 조금 더 자세하게 알고리즘을 코드로 구현하는 방법에 대해 알아보겠습니다!!

 

기본적인 알고리즘의 구성은 간선을 담은 2차원 배열, 최단경로를 담은 1차원 배열로 구성됩니다.

만약 우선순위 큐를 사용하지 않는다면 이미 방문한 점을 다시 방문하지 않기 위한 체크용 1차원 배열이 필요할 수 있습니다. (저는 우선순위 큐를 사용한 방식만을 설명하겠습니다!!

 

0. 간선들을 이차원 배열 v에 저장합니다. (간선의 weight도 같이 저장해줍니다.)

1. 최단거리를 저장할 배열 dist를 만들고, 전부 최대값(INF)를 넣어줍니다.

2. 출발 지점을 선택합니다. (함수 형태로 동작하게 만들어서 시작지점을 start라는 매개변수로 넘겨주는 방식을 사용했습니다.)

3. pq를 생성합니다. (weight, start)를 저장하고, 오름차순으로 정렬되도록 설정합니다.

4. 출발지점을 pq에 등록합니다. pq에 들어가는 요소는 현재까지의 최단거리와 start인데, 맨 첫 요소는 자기 자신이기 때문에 0을 넣어줍니다.

5. 이제 pq에 들어간 요소가 없어질 때까지 반복해서 pq에서 요소를 뽑아냅니다. 뽑아내는 요소는 선택된 vertex(curr)와 weight(w)가 됩니다. (여기서 pq에 의해서 항상 O(logN)만큼의 시간복잡도로 weight순으로 정렬이 됩니다.)

6. pq에서 값을 뽑았으면 해당하는 부분을 pq에서 제거합니다.

7. curr에서 시작하는 모든 간선을 확인합니다. 그리고 w+v[curr][도착점]이 dist[도착점]보다 작다면 dist를 업데이트하고, pq에 (업데이트한 weight, 도착점)을 넣습니다.

8. 위 작업을 pq가 빌 때까지 반복합니다. 그렇게 동작이 끝나면 dist에는 start로부터 출발했을 때 모든 점들의 최단거리가 저장됩니다.

 

시간복잡도를 계산해보면 모든 간선을 확인(O(E))해서 pq를 이용해서 최단거리를 갱신(O(logE))하는 데에 O(ElogE)가 걸리게 됩니다.

pq를 이용해서 이미 방문한 시작 vertex은 더이상 방문하지 않으므로, 정확히 E번의 간선을 1번씩 확인하게 되고, pq를 삽입하는 과정에서 생기는 O(logE)시간이 걸린다고 생각하시면 됩니다. (매번 pq를 갱신한다고 가정했을 때!!)

 

중복 간선(출발지와 목적지가 같은 간선)이 없다면 E는 최대 V^2이 됩니다. (자기 자신을 포함한 V개의 vertex로 이어지는 간선을 V번만큼 이어줘야 하니까요!!)

만약 E자리에 V^2를 넣으면 O(ElogE)는 O(2ElogV)가 되는데, 빅오 표기법에 따라 O(ElogV)라고 표기할 수 있겠네요!

 

---

2. 실제 코드

가장 기본적인 문제인 백준의 1916번 최소비용 구하기 문제를 가져왔습니다!

위에 설명한 내용에 맞게 코드를 작성했으니, 참고하시면 될 것 같습니다!

다익스트라 함수 내부에 존재하는

if (dist[curr] < w) continue;

부분은 불필요한 간선 확인을 없애기 위한 pruning이 추가된 부분이라고 생각하시면 됩니다!

 

1916번: 최소비용 구하기

 

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


vector<pair<int, int>> v[1001]; // 간선 담은 벡터
int dist[1001]; // 최단거리 배열

void dijkstra(int start) {
    for (int i = 0; i < 1001; ++i) {
        dist[i] = 100000000; // 하나의 간선의 길이가 1 이상 100000 이하이고, 최악의 경우 999개의 간선을 통해 도시가 연결될 수 있으므로 99900000을 초과하는 값이 들어가야 하므로 1억을 대입
    }

    // pq를 사용하기 때문에 굳이 방문 여부를 확인하지 않아도 된다! (어짜피 이미 최소값이 등록되었기 때문에 pq로 해당 도착점이 새롭게 추가 될 일이 없기 때문!!)
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 오름차순 pq 등록 (pair 앞은 weight, 뒤는 vertex - 도착점)
    pq.push(make_pair(0, start)); // 시작점 등록

    while (!pq.empty()) {
        int w = pq.top().first; // 가장 우선순위가 높은 점의 dist를 추출해서 w에 저장
        int curr = pq.top().second; // 가장 우선순위가 높은 vertex를 curr에 등록
        pq.pop(); // 값을 추출했으니 pq에서 제거
        
        if (dist[curr] < w) continue; // w가 기존 비용보다 크면 통과
        for (int i = 0; i < v[curr].size(); ++i) { // curr에서 시작하는 간선을 모두 탐색
            int nextw = w + v[curr][i].first; // 그 간선으로 연결된 도착 vertex까지의 거리 (다익스트라 시작점 ~ start까지는 반드시 최단거리)
            int nextv = v[curr][i].second; // 그 간선의 도착 vertex
            if (nextw < dist[nextv]) { // 만약 기존 최단거리보다 더 짧은 거리로 해당 도착지점에 도착할 수 있다면
                dist[nextv] = nextw; // dist 최단거리 배열값 업데이트
                pq.push(make_pair(nextw, nextv)); // 추가 업데이트를 위해 업데이트된 거리와 도착지점 pq에 등록
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    // 1916 최소비용 구하기
    // 다익스트라

    int n, m, start, end, w;
    cin >> n >> m;

    // 연결된 간선 등록
    for (int i = 0; i < m; ++i) {
        cin >> start >> end >> w;
        v[start].push_back(make_pair(w, end));
    }

    // 출발점과 끝점 입력받기
    int s, e;
    cin >> s >> e;

    // 다익스트라 구하기 (s부터 시작하는 최단경로 계산)
    dijkstra(s);

    cout << dist[e]; // s부터 e까지 가는 최소비용 출력

    return 0;
}