[Algorithm] 다익스트라 알고리즘
in Algorithm
다익스트라 알고리즘에 대해 정리해보았습니다. 한 정점에서 모든 정점까지의 최단 경로를 구하는 대표 알고리즘입니다.
최단 경로 시리즈 – 플로이드-워셜(모든 쌍), 벨만-포드(음수 간선·음수 사이클)에 이어, 한 출발점에서 나머지 모든 정점까지의 최단 경로를 빠르게 구하는 알고리즘이다.
🎯 1️⃣ 다익스트라란?
💡 한 문장 정의
“음수 간선이 없을 때, 한 출발점에서 모든 정점까지의 최단 경로를 구하는 그리디 알고리즘”
💡 언제 사용하는가?
- 한 정점(출발점)에서 나머지 모든 정점까지의 최단 거리가 필요할 때
- 간선 가중치가 모두 0 이상(비음수)일 때
- 정점·간선이 많아서 플로이드-워셜 O(V³)을 쓰기 어려울 때
💡 특징
| 특징 | 설명 |
|---|---|
| 시간복잡도 | O((V+E)log V) (우선순위 큐 사용 시) |
| 공간복잡도 | O(V) |
| 음수 간선 | 불가능 (잘못된 결과 가능) |
| 그래프 종류 | 방향/무방향 모두 가능 |
| 구현 난이도 | 중간 (우선순위 큐 활용) |
| 성격 | 그리디 (매 순간 가장 가까운 정점 확정) |
🧠 2️⃣ 핵심 개념 이해하기
💡 알고리즘의 본질
"매 단계마다 '가장 거리가 짧은 정점'을 하나씩 확정하고,
그 정점을 통해 갈 수 있는 이웃들의 거리를 갱신해 나가는 알고리즘"
💡 dist[v]의 의미
dist[v] = 출발점(start)으로부터
정점 v까지 도달하는 현재까지의 최소 비용
- 한 번 확정(방문 처리)한 정점의 dist 값은 더 이상 바뀌지 않는다.
- 음수 간선이 없기 때문에, “지금 가장 작은 dist를 가진 정점”은 이미 최단 거리가 보장된다.
💡 그리디한 선택
- “현재 시점에서 dist가 가장 작은 정점”을 골라서 확정한다.
- 그 정점을 거쳐 가는 경로가 더 짧아질 수 있는 이웃만 완화(relax)한다.
- 이렇게 하면 각 정점을 최대 한 번씩만 확정 처리하면 되고, 우선순위 큐로 “가장 작은 dist”를 빠르게 꺼낼 수 있다.
🔁 3️⃣ 간선 완화(Relaxation)
💡 간선 완화란?
“간선 u → v를 이용했을 때, 출발점에서 v까지 가는 거리가 더 짧아지면 dist[v]를 갱신하는 과정”
(벨만-포드, 플로이드-워셜에서 쓰는 것과 같은 개념이다.)
💡 완화 조건
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
// 우선순위 큐 사용 시: (dist[v], v) 다시 넣거나 갱신
}
u: 방금 확정한 정점v: u의 이웃 정점w: 간선 (u, v)의 가중치
📌 4️⃣ 우선순위 큐와 동작 과정
💡 왜 우선순위 큐를 쓰는가?
- 매번 “dist가 가장 작은 정점”을 골라야 한다.
- 배열로 매번 최솟값을 찾으면 O(V) → 전체 O(V²).
- 우선순위 큐(최소 힙)를 쓰면 최솟값 추출 O(log V), 간선당 최대 1번 갱신 → O((V+E)log V).
💡 동작 흐름 (요약)
- 출발점
start의dist[start] = 0, 나머지는 무한대(INF)로 초기화. - 우선순위 큐에
(0, start)넣기. (비용, 정점 번호) - 큐가 빌 때까지:
- 비용이 가장 작은 (d, u) 꺼내기.
- 이미
d > dist[u]이면 스킵 (예전에 넣은 쓸모없는 정보). - u를 확정했다고 보고, u와 연결된 각 간선 (u → v, 가중치 w)에 대해 완화.
- 완화로
dist[v]가 줄어들면(dist[v], v)를 큐에 넣기.
- 종료 후
dist[]가 출발점에서 각 정점까지의 최단 거리.
💡 “확정”의 의미
- 음수 간선이 없으므로, 현재 dist가 가장 작은 정점은 더 이상 다른 경로로 더 짧아질 수 없다.
- 그래서 그 정점은 한 번만 꺼내서 이웃만 완화하면 되고, 다시 큐에 넣을 필요 없다.
d > dist[u]인 경우는 “예전에 넣었던 더 나쁜 값”이므로 무시한다.
💻 5️⃣ 코드 구현
💡 인접 리스트 + 우선순위 큐 (Java)
import java.util.*;
class Dijkstra {
static final int INF = 987654321;
List<int[]>[] graph; // graph[v] = { {next, cost}, ... }
int[] dist;
int V;
public int[] dijkstra(int start) {
dist = new int[V + 1];
Arrays.fill(dist, INF);
dist[start] = 0;
// (비용, 정점) - 비용 기준 최소 힙
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
pq.offer(new int[]{0, start});
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int d = cur[0], u = cur[1];
if (d > dist[u]) continue; // 이미 더 좋은 경로로 갱신된 경우 스킵
for (int[] edge : graph[u]) {
int v = edge[0], w = edge[1];
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.offer(new int[]{dist[v], v});
}
}
}
return dist;
}
}
💡 인접 행렬 버전 (정점 수가 작을 때)
- 정점이 적고 간선이 많을 때는 인접 행렬 + 매번 최솟값 탐색으로도 구현 가능.
- 시간복잡도 O(V²). 플로이드-워셜보다는 V가 클 때 유리할 수 있다.
⏱️ 6️⃣ 시간복잡도와 공간복잡도
💡 우선순위 큐 버전
| 구분 | 복잡도 | 설명 |
|---|---|---|
| 시간복잡도 | O((V+E) log V) | 각 간선 최대 1번 완화, PQ 삽입/삭제 log V |
| 공간복잡도 | O(V) | dist[], PQ에 정점 개수만큼 |
💡 인접 행렬 + 선형 탐색 버전
| 구분 | 복잡도 | 설명 |
|---|---|---|
| 시간복잡도 | O(V²) | V번 반복, 매번 O(V) 최솟값 |
| 공간복잡도 | O(V²) | 인접 행렬 |
⚖️ 7️⃣ 벨만-포드·플로이드-워셜과의 비교
| 구분 | 다익스트라 | 벨만-포드 | 플로이드-워셜 |
|---|---|---|---|
| 목적 | 한 출발점 → 모든 정점 | 한 출발점 → 모든 정점 | 모든 쌍 최단 경로 |
| 음수 간선 | 불가능 | 가능 | 가능 (음수 사이클 제외) |
| 음수 사이클 | 해당 없음 | 탐지 가능 | 있으면 사용 불가 |
| 시간복잡도 | O((V+E)log V) 또는 O(V²) | O(VE) | O(V³) |
| 공간복잡도 | O(V) | O(V) | O(V²) |
| 적용 상황 | 출발점 하나, 음수 간선 없음 | 음수 간선/사이클 | 정점 적을 때, 모든 쌍 |
💡 언제 무엇을 쓸까?
🧪 8️⃣ 실전 문제 적용
💡 대표 문제 유형
| 유형 | 설명 | 예시 키워드 |
|---|---|---|
| 단일 출발 최단 경로 | 한 도시에서 다른 모든 도시까지 | “1번 노드에서”, “한 점에서” |
| 가중치가 양수 | 거리, 시간, 비용이 0 이상 | “최소 비용”, “최단 거리” |
| 경로 복원 | 최단 경로에 포함된 정점/간선 출력 | “경로 출력”, “경로 추적” |
| 2차원 격자 | 칸 이동 비용을 간선으로 두고 적용 | “다익스트라 + BFS/격자” |
💡 체크리스트
다익스트라를 쓸 때 확인할 것:
- 음수 간선이 없는가? (있으면 벨만-포드)
- 한 출발점에서 나머지 전체가 필요한가? (모든 쌍이면 플로이드-워셜 고려)
INF값을 충분히 크게 설정했는가?- 같은 정점에 대한 중복 간선이 있으면 더 작은 가중치만 남겼는가?
d > dist[u]스킵 처리로 이미 갱신된 노드를 건너뛰었는가?
이렇게 다익스트라까지 정리하면, 플로이드-워셜·벨만-포드와 함께 최단 경로 시리즈를 한 세트로 다룰 수 있다.
