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

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

 : 하나의 정점에서 출발하여 그래프상의 다른 모든 정점까지의 최단 경로를 찾는 알고리즘을 말한다. 이때, 두 가지 전제 조건이 있다.

1. 가중치(weight)가 있는 그래프에서 사용한다.

2. 모든 가중치는 0 이상이어야 한다. (음수 가중치 X.)

 

다익스트라 알고리즘은 그리디 알고리즘에 속한다. 그리디 알고리즘은 "지금 가장 이득이 되는 선택이 최선의 결과로 이어진다"는 접근 방식이다. 다익스트라 알고리즘이 진행되는 과정은 다음과 같다.

1. 출발점에서 아직 방문하지 않은 노드들까지의 최단 거리를 모두 계산한다.

2. 그중에서 가장 거리가 짧은 노드를 선택하여 방문한다.

3. 방문한 노드는 최단 거리가 확정된 노드로 처리하고, 이 노드를 거쳐가는 것이 더 빠른 경로가 있다면 주변 노드들의 거리를 갱신한다.

4. 모든 노드를 방문할 때까지 이를 반복한다.

 

다익스트라 알고리즘의 핵심은 한 번 최단 거리가 확정된 노드의 최단 거리는 다시 계산하지 않는다는 것이다. 모든 가중치가 0 이상이기 때문에 그 거리가 더 이상 줄어들지 않기 때문이다. 그렇다면 이제 다익스트라 알고리즘을 구현하는 방법에 대해 알아보자. 두 노드 사이의 거리는 배열 v에 저장되어 있다고 하자. v[i][j]는 노드 i와 노드 j 사이의 거리를 말한다.

---

 1️⃣ 배열을 이용한 구현

 : 가장 직관적이면서도 이해하기 쉬운 구현 방식이다. 시간 복잡도는 $O(N^2)$이다.

- dis[i]: 시작점에서 i번 노드까지의 최단 거리를 저장한다. 무한(INF)로 초기화하고, 시작점은 0으로 설정한다.

- visited[i]: i번 노드의 최단 거리가 확정되었는지 여부를 저장한다.

 

 ✅ 동작 순서

1. 노드 선택: visited가 false인 노드 중에서 dis 값이 가장 작은 노드를 선택한다. (cur)

2. 방문 처리: visited[cur]를 true로 변경한다.

3. 거리 갱신: cur와 연결된 모든 주변 노드(neighbor)에 대해 기존 dis 값보다 cur을 거쳤을 때의 값이 더 짧다면 dis[nei]를 갱신한다.

- dis[nei]=min(dis[nei], v[cur][nei]+dis[cur])

4. 반복: 위 1~3을 N번 반복한다.

for (int i = 1; i <= N; i++) {
        int cur = -1, min_val = INF;
        for (int j = 1; j <= N; j++) {
            if (visited[j] == false && dis[j] < min_val) {  // dis 값이 가장 작은 노드 선택.
                min_val = dis[j];
                cur = j;
            }
        }
        if (cur == -1) break;
        visited[cur] = true; // 방문 처리.
        for (int j = 1; j <= N; j++) {  // 거리 갱신.
            if (visited[j] == false && dis[j] > dis[cur] + v[cur][j])
                dis[j] = dis[cur] + v[cur][j];
        }
    }
}

 2️⃣ 우선순위 큐를 이용한 구현

: 배열 구현의 시간 복잡도 $O(N^2)$의 원인인 '노드 선택' 과정을 최적화한 방식이다. 시간 복잡도는 $O(E log N)$이다. 이때, E는 간선의 개수를 의미한다. min-heap을 이용하여 구현한다.

- visited 배열 대신 dis 값을 비교하여 방문 여부를 확인한다.

- 우선순위 큐에 (거리, 노드) 쌍을 저장하여 거리가 가장 짧은 노드가 항상 top에 오도록 한다.

 

 ✅ 동작 순서

1. 초기화: dis 배열을 모두 무한(INF)로 초기화한다.

2. 시작점 설정: dis[start]=0으로 설정하고, 우선순위 큐에 (0, start)를 삽입한다.

3. 최단 거리 노드 선택: 우선순위 큐에서 pop()하여 (cur_dis, cur)을 꺼낸다.

4. 최적화: cur_dis가 dis[cur]보다 크면, 이미 최단 거리가 발견된 정보이므로 무시한다. (continue)

5. 거리 갱신: cur와 연결된 모든 주변 노드(neighbor)에 대해 기존 dis 값보다 cur을 거쳤을 때의 값이 더 짧다면 dis[nei]를 갱신하고, 우선순위 큐에 삽입한다.

- if(dis[nei]>v[cur][nei]+dis[cur]

ㅤㅤdis[nei]=v[cur][nei]+dis[cur]

ㅤㅤ우선순위 큐에 (dis[nei], nei)를 push().

6. 반복: 위 3~5을 우선순위 큐가 비워질 때까지 반복한다.

---

 ⛳️ 비교

비교 항목	배열	우선순위 큐
핵심 동작	전체 노드를 스캔하여 최단 거리 노드 찾기.	PQ를 이용해 최단 거리 노드를 빠르게 pop.
시간 복잡도	$O(N^2)$	$O(E log N)$
적합한 경우	- N이 매우 작을 때 ($N < 2000$) - 그래프가 매우 빽빽할 때	- N이 클 때 ($N > 5000$) - 일반적인 코딩 테스트 환경

---

✍🏻 관련 문제

 ❓ 문제

백준 1916번: 최소비용 구하기 https://www.acmicpc.net/problem/1916

백준 13549번: 숨바꼭질 3 https://www.acmicpc.net/problem/13549

백준 1504번: 특정한 최단 경로 https://www.acmicpc.net/problem/1504

백준 1753번: 최단경로 https://www.acmicpc.net/problem/1753

백준 14938번: 서강그라운드 https://www.acmicpc.net/problem/14938

백준 1238번: 파티 https://www.acmicpc.net/problem/1238

백준 11779번: 최소비용 구하기 2 https://www.acmicpc.net/problem/11779

 

 💡문제풀이

[BOJ C++] 백준 1916번: 최소비용 구하기