다익스트라 알고리즘은 에츠허르 다이크스트라가 1956년 단 20분 만에 고안한 알고리즘으로, 70년이 지난 지금도 네비게이션·네트워크 라우팅·게임 AI·물류 시스템의 핵심에서 작동하고 있습니다. 코딩 테스트에서는 최단 경로 문제의 표준 풀이로, 개발자 면접에서는 그래프 알고리즘 이해의 기준선으로 자리 잡았습니다. “그냥 BFS에 가중치 추가한 것 아닌가요?”라는 질문부터, “왜 음수 가중치에서는 작동하지 않나요?”, “힙을 쓰면 왜 빨라지나요?”까지 — 이 질문들에 논리적으로 답할 수 있어야 진짜 이해한 것입니다. 이 글에서는 알고리즘의 핵심 원리를 시각화와 함께 단계별로 해체하고, 최적화된 실전 코드와 실무 적용 사례까지 완전히 정리합니다.
목차
- 다이크스트라 알고리즘이란 – 핵심 아이디어와 전제 조건
- 동작 원리 – 단계별 시각화로 완전 이해
- 코드 구현 – 나이브 버전부터 우선순위 큐 최적화까지
- 시간·공간 복잡도 분석 – 왜 힙이 필수인가
- 한계와 변형 – 음수 가중치·벨만포드·A* 비교
- 실무 적용 – 네비게이션·네트워크·게임 실전 사례
1. 다이크스트라 알고리즘이란 – 핵심 아이디어와 전제 조건
다이크스트라 알고리즘을 제대로 이해하려면 이 알고리즘이 어떤 문제를 풀고, 어떤 핵심 아이디어로 동작하는지부터 파악해야 합니다.
해결하는 문제 – 단일 출발점 최단 경로
다이크스트라 알고리즘은 단일 출발점 최단 경로(Single Source Shortest Path, SSSP) 문제를 풉니다. 가중치 있는 그래프에서 하나의 출발 노드로부터 모든 다른 노드까지의 최단 거리를 구합니다.
문제 예시:
서울에서 출발해 부산·대구·광주·인천까지 각각 최단 거리는?
그래프 표현:
서울 ─15─ 대전 ─10─ 대구 ─10─ 부산
└──20──────────────────────────────┘
서울 ─25─ 광주
서울 ─10─ 인천단순히 “가장 적은 홉(hop) 수”를 찾는 BFS와 달리, 다이크스트라는 **간선마다 다른 비용(가중치)**을 고려해 진짜 최소 비용 경로를 찾습니다.
핵심 아이디어 – 그리디 + 완화(Relaxation)
다이크스트라의 핵심은 두 가지 아이디어의 결합입니다.
첫째, **탐욕적 선택(Greedy Choice)**입니다. 매 단계에서 아직 처리하지 않은 노드 중 현재까지 발견된 최단 거리가 가장 짧은 노드를 선택합니다. 이 선택이 왜 옳은가? 모든 가중치가 양수라면, 이 노드의 최단 거리는 이후에 더 짧아질 수 없기 때문입니다. 음수 간선이 없다면, 다른 경로를 통해 우회해봤자 현재 최솟값보다 더 짧을 수 없습니다.
둘째, **완화(Relaxation)**입니다. 선택된 노드를 거쳐 인접 노드로 가는 거리를 계산하고, 기존에 알려진 거리보다 짧으면 업데이트합니다.
완화 공식:
if dist[u] + weight(u, v) < dist[v]:
dist[v] = dist[u] + weight(u, v)
# "u를 경유해서 v로 가는 것이 더 빠르면 업데이트"이 두 아이디어가 반복되며 출발점에서 모든 노드까지의 최단 거리가 확정됩니다.
전제 조건 – 반드시 알아야 할 제약
다이크스트라 알고리즘이 정확하게 동작하려면 중요한 전제가 있습니다.
모든 간선의 가중치가 0 이상의 양수여야 합니다. 음수 가중치가 있으면 이미 처리한 노드의 최단 거리가 나중에 더 짧아질 수 있어, 탐욕적 선택의 전제가 깨집니다. 음수 가중치가 있는 그래프에는 벨만-포드 알고리즘을 사용해야 합니다.
2. 동작 원리 – 단계별 시각화로 완전 이해
다음 그래프를 예제로 노드 A에서 출발하는 최단 경로를 단계별로 추적합니다.
그래프 구조 (무방향 가중치 그래프):
4 2
A ──── B ──── D
│ │ │
2│ 1│ 3│
│ │ │
C ──── E ──── F
5 1
간선 목록:
A-B: 4 A-C: 2
B-D: 2 B-E: 1
C-E: 5
D-F: 3 E-F: 1STEP 0 – 초기화
dist = {A: 0, B: ∞, C: ∞, D: ∞, E: ∞, F: ∞}
visited = {}
우선순위 큐: [(0, A)]
# 출발 노드 A의 거리 = 0, 나머지는 무한대로 초기화STEP 1 – A 선택 및 인접 노드 완화
큐에서 최소 거리 노드 꺼냄: A (dist=0)
visited = {A}
A의 인접 노드 완화:
B: dist[A] + 4 = 0 + 4 = 4 < ∞ → dist[B] = 4 ✓
C: dist[A] + 2 = 0 + 2 = 2 < ∞ → dist[C] = 2 ✓
dist = {A: 0, B: 4, C: 2, D: ∞, E: ∞, F: ∞}
우선순위 큐: [(2, C), (4, B)]STEP 2 – C 선택 (거리 2로 최솟값)
큐에서 최소 거리 노드 꺼냄: C (dist=2)
visited = {A, C}
C의 인접 노드 완화:
E: dist[C] + 5 = 2 + 5 = 7 < ∞ → dist[E] = 7 ✓
(A는 이미 visited → 건너뜀)
dist = {A: 0, B: 4, C: 2, D: ∞, E: 7, F: ∞}
우선순위 큐: [(4, B), (7, E)]STEP 3 – B 선택 (거리 4)
큐에서 최소 거리 노드 꺼냄: B (dist=4)
visited = {A, C, B}
B의 인접 노드 완화:
D: dist[B] + 2 = 4 + 2 = 6 < ∞ → dist[D] = 6 ✓
E: dist[B] + 1 = 4 + 1 = 5 < 7 → dist[E] = 5 ✓ (갱신!)
dist = {A: 0, B: 4, C: 2, D: 6, E: 5, F: ∞}
우선순위 큐: [(5, E), (6, D), (7, E_old)]
# (7, E)는 이미 dist[E]=5로 갱신됐으므로 나중에 건너뜀STEP 4 – E 선택 (거리 5)
큐에서 최소 거리 노드 꺼냄: E (dist=5)
visited = {A, C, B, E}
E의 인접 노드 완화:
F: dist[E] + 1 = 5 + 1 = 6 < ∞ → dist[F] = 6 ✓
(C, B는 이미 visited → 건너뜀)
dist = {A: 0, B: 4, C: 2, D: 6, E: 5, F: 6}
우선순위 큐: [(6, D), (6, F), (7, E_old)]STEP 5 – D 선택 (거리 6)
큐에서 최소 거리 노드 꺼냄: D (dist=6)
visited = {A, C, B, E, D}
D의 인접 노드 완화:
F: dist[D] + 3 = 6 + 3 = 9 > 6 → 갱신 없음 (이미 더 짧음)
dist = {A: 0, B: 4, C: 2, D: 6, E: 5, F: 6}STEP 6 – F 선택 (거리 6, 완료)
F 선택 → 모든 노드 처리 완료
최종 최단 거리:
A → A: 0
A → C: 2 (경로: A → C)
A → B: 4 (경로: A → B)
A → E: 5 (경로: A → B → E)
A → D: 6 (경로: A → B → D)
A → F: 6 (경로: A → B → E → F)3. 코드 구현 – 나이브 버전부터 우선순위 큐 최적화까지
구현 1 – 나이브(Naive) 버전: O(V²)
python
# 인접 행렬 기반 - 소규모 그래프에서 이해하기 쉬운 버전
import math
def dijkstra_naive(graph, start):
"""
graph: 인접 행렬 (graph[u][v] = 가중치, 없으면 inf)
start: 출발 노드 인덱스
"""
n = len(graph)
dist = [math.inf] * n # 최단 거리 배열
dist[start] = 0
visited = [False] * n # 처리 완료 여부
for _ in range(n):
# 미방문 노드 중 최단 거리 노드 선택 - O(V)
u = -1
for v in range(n):
if not visited[v]:
if u == -1 or dist[v] < dist[u]:
u = v
if u == -1 or dist[u] == math.inf:
break # 더 이상 연결된 노드 없음
visited[u] = True
# u의 인접 노드 완화 - O(V)
for v in range(n):
if graph[u][v] != math.inf and not visited[v]:
new_dist = dist[u] + graph[u][v]
if new_dist < dist[v]:
dist[v] = new_dist
return dist
# 사용 예시
INF = math.inf
graph = [
# A B C D E F
[INF, 4, 2, INF, INF, INF], # A
[ 4, INF, INF, 2, 1, INF], # B
[ 2, INF, INF, INF, 5, INF], # C
[INF, 2, INF, INF, INF, 3 ], # D
[INF, 1, 5, INF, INF, 1 ], # E
[INF, INF, INF, 3, 1, INF], # F
]
result = dijkstra_naive(graph, start=0)
nodes = ['A', 'B', 'C', 'D', 'E', 'F']
for i, d in enumerate(result):
print(f"A → {nodes[i]}: {d}")
# A → A: 0 A → B: 4 A → C: 2
# A → D: 6 A → E: 5 A → F: 6구현 2 – 우선순위 큐 최적화 버전: O((V+E) log V)
python
import heapq
from collections import defaultdict
def dijkstra_heap(graph, start, n):
"""
graph: 인접 리스트 {u: [(v, weight), ...]}
start: 출발 노드
n: 전체 노드 수
반환: dist (최단 거리 배열), prev (이전 노드 배열, 경로 추적용)
"""
dist = [float('inf')] * n
dist[start] = 0
prev = [-1] * n # 경로 역추적을 위한 이전 노드
visited = [False] * n
# 최소 힙: (거리, 노드)
heap = [(0, start)]
while heap:
d, u = heapq.heappop(heap) # 가장 짧은 거리 노드 꺼냄
# ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
# 핵심: 이미 처리된 노드 건너뜀
# 힙에 중복으로 들어간 (구거리, 노드) 처리
# ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
if visited[u]:
continue
visited[u] = True
# u의 인접 노드 완화
for v, weight in graph[u]:
new_dist = dist[u] + weight
if new_dist < dist[v]:
dist[v] = new_dist
prev[v] = u
heapq.heappush(heap, (new_dist, v))
# 힙에 (새거리, v) 추가
# 기존 (구거리, v)는 그대로 힙에 남아 있지만
# visited[v]=True 체크로 나중에 건너뜀
return dist, prev
def reconstruct_path(prev, start, end):
"""prev 배열로 최단 경로 역추적"""
path = []
node = end
while node != -1:
path.append(node)
node = prev[node]
path.reverse()
# 시작 노드까지 경로가 있는지 확인
if path[0] == start:
return path
return [] # 연결되지 않은 경우
# ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
# 사용 예시 (인접 리스트 표현)
# ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
graph = defaultdict(list)
edges = [
(0, 1, 4), (0, 2, 2), # A-B:4, A-C:2
(1, 0, 4), (1, 3, 2), (1, 4, 1), # B-A, B-D:2, B-E:1
(2, 0, 2), (2, 4, 5), # C-A, C-E:5
(3, 1, 2), (3, 5, 3), # D-B, D-F:3
(4, 1, 1), (4, 2, 5), (4, 5, 1), # E-B, E-C, E-F:1
(5, 3, 3), (5, 4, 1), # F-D, F-E
]
for u, v, w in edges:
graph[u].append((v, w))
dist, prev = dijkstra_heap(graph, start=0, n=6)
nodes = ['A', 'B', 'C', 'D', 'E', 'F']
print("=== 최단 거리 ===")
for i, d in enumerate(dist):
path = reconstruct_path(prev, 0, i)
path_str = " → ".join(nodes[p] for p in path)
print(f"A → {nodes[i]}: {d} (경로: {path_str})")
# 출력:
# A → A: 0 (경로: A)
# A → B: 4 (경로: A → B)
# A → C: 2 (경로: A → C)
# A → D: 6 (경로: A → B → D)
# A → E: 5 (경로: A → B → E)
# A → F: 6 (경로: A → B → E → F)구현 3 – Java 버전 (코딩 테스트 실전형)
java
import java.util.*;
public class Dijkstra {
static final int INF = Integer.MAX_VALUE;
/**
* 다이크스트라 알고리즘 (우선순위 큐 최적화)
* @param graph 인접 리스트 List<int[]>[] (int[]{목적지, 가중치})
* @param start 출발 노드
* @param n 전체 노드 수
* @return 최단 거리 배열
*/
public static int[] dijkstra(List<int[]>[] graph, int start, int n) {
int[] dist = new int[n];
Arrays.fill(dist, INF);
dist[start] = 0;
// int[]{거리, 노드} 기준으로 거리 오름차순 정렬
PriorityQueue<int[]> pq = new PriorityQueue<>(
Comparator.comparingInt(a -> a[0])
);
pq.offer(new int[]{0, start});
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int d = curr[0];
int u = curr[1];
// 이미 처리된 노드 건너뜀 (중복 처리 방지)
if (d > dist[u]) continue;
// 인접 노드 완화
for (int[] edge : graph[u]) {
int v = edge[0];
int weight = edge[1];
int newDist = dist[u] + weight;
if (newDist < dist[v]) {
dist[v] = newDist;
pq.offer(new int[]{newDist, v});
}
}
}
return dist;
}
public static void main(String[] args) {
int n = 6; // A=0, B=1, C=2, D=3, E=4, F=5
@SuppressWarnings("unchecked")
List<int[]>[] graph = new ArrayList[n];
for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
// 간선 추가 (무방향)
int[][] edges = {
{0,1,4},{0,2,2},{1,3,2},{1,4,1},
{2,4,5},{3,5,3},{4,5,1}
};
for (int[] e : edges) {
graph[e[0]].add(new int[]{e[1], e[2]});
graph[e[1]].add(new int[]{e[0], e[2]}); // 무방향이므로 역방향도
}
int[] result = dijkstra(graph, 0, n);
String[] names = {"A","B","C","D","E","F"};
for (int i = 0; i < n; i++) {
System.out.printf("A → %s: %d%n", names[i], result[i]);
}
}
}4. 시간·공간 복잡도 분석 – 왜 힙이 필수인가
복잡도 비교
| 구현 방식 | 시간 복잡도 | 공간 복잡도 | 적합한 상황 |
|---|---|---|---|
| 나이브 (인접 행렬) | O(V²) | O(V²) | V ≤ 1,000의 밀집 그래프 |
| 우선순위 큐 (인접 리스트) | O((V+E) log V) | O(V+E) | V, E가 큰 희소 그래프 |
| 피보나치 힙 | O(V log V + E) | O(V+E) | 이론적 최적 (구현 복잡) |
왜 나이브 버전이 O(V²)인가
나이브 버전의 두 핵심 연산:
1. 최소 거리 노드 선택: 전체 V개 노드를 선형 탐색 → O(V)
2. 이 작업을 V번 반복 (각 노드를 한 번씩 처리)
총 시간: O(V) × O(V) = O(V²)V가 10,000이면 연산 횟수는 100,000,000번 — 0.1초 제한 코테에서는 통과 불가능합니다.
왜 힙 버전이 O((V+E) log V)인가
힙 버전의 핵심 연산:
1. 힙에서 최솟값 꺼내기: O(log V)
→ 최대 V+E번 발생 (각 간선마다 최대 1번 push)
2. 힙에 삽입 (완화 시): O(log V)
→ 최대 E번 발생
총 시간: O((V+E) log V)
E가 V²에 가까운 밀집 그래프: O(V² log V) — 나이브보다 느림
E가 V에 가까운 희소 그래프: O(V log V) — 나이브보다 훨씬 빠름실제 코딩 테스트와 실무의 그래프는 대부분 희소 그래프이므로, 힙 버전이 표준입니다.
힙의 중복 노드 문제와 해결
python
# 완화 시 힙에 중복 추가 발생 가능
# 예: E의 거리가 7→5로 갱신될 때
heap = [(7, E)] # 구버전
heapq.heappush(heap, (5, E))
heap = [(5, E), (7, E)] # 둘 다 존재
# 해결: 꺼낼 때 visited 체크 또는 거리 비교
d, u = heapq.heappop(heap) # (5, E) 꺼냄
if d > dist[u]: continue # dist[E]=5이므로 d==5, 처리
...
d, u = heapq.heappop(heap) # (7, E) 꺼냄
if d > dist[u]: continue # dist[E]=5 < 7 → 건너뜀 ✓이 중복 처리가 없으면 같은 노드가 여러 번 처리되어 결과는 맞지만 성능이 저하됩니다.
5. 한계와 변형 – 음수 가중치·벨만포드·A* 비교
음수 가중치에서 다이크스트라가 실패하는 이유
음수 간선 포함 그래프:
A →(1)→ B →(-5)→ C
A →(3)→ C
다이크스트라 진행:
1. A 선택, dist = {A:0, B:1, C:3}
2. B 선택 (dist=1), C 완화: 1+(-5) = -4 → dist[C] = -4
❌ 문제: B를 선택할 당시 C=3으로 이미 "처리됨" 처리했다면
C의 실제 최단거리 -4를 놓칩니다.
핵심 이유:
- 탐욕적 선택의 전제: "지금 가장 짧은 노드는 이후 더 짧아질 수 없다"
- 음수 간선이 있으면 이 전제가 깨짐
- B(dist=1)를 선택한 이후, B를 경유한 경로가 기존 선택보다 짧아질 수 있음알고리즘별 비교
| 알고리즘 | 시간복잡도 | 음수 가중치 | 음수 사이클 감지 | 적합 상황 |
|---|---|---|---|---|
| 다이크스트라 | O((V+E) log V) | ❌ 불가 | ❌ | 양수 가중치 희소 그래프 |
| 벨만-포드 | O(VE) | ✅ 가능 | ✅ | 음수 가중치, 분산 시스템 |
| Floyd-Warshall | O(V³) | ✅ 가능 | ✅ | 모든 쌍 최단 경로, 소규모 |
| A* | O(E log V) | ❌ 불가 | ❌ | 목적지가 하나, 휴리스틱 사용 |
A* 알고리즘과의 핵심 차이
다이크스트라는 목적지 없이 모든 노드의 최단 거리를 구합니다. A*는 목적지가 하나일 때 **휴리스틱 함수(h)**를 사용해 목적지 방향을 우선 탐색합니다.
python
# 다이크스트라: 우선순위 = 출발점까지 거리 g(n)
priority = g(n)
# A*: 우선순위 = 출발점까지 거리 + 목적지 추정 거리
priority = g(n) + h(n)
# h(n): 현재 노드에서 목적지까지의 추정 거리 (예: 직선거리)
# A*는 목적지 방향으로 편향해 탐색 → 불필요한 노드 탐색 감소
# 단, h(n)이 실제 거리를 절대 과대추정하면 안 됨 (admissible)네비게이션 앱에서 목적지가 하나인 경우 A*, 대중교통 환승 경로 같이 중간 경유지가 많은 경우 다이크스트라를 변형한 알고리즘을 사용합니다.
6. 실무 적용 – 네비게이션·네트워크·게임 실전 사례
사례 ① 네비게이션 경로 탐색
python
# 도로 네트워크에서의 다이크스트라 적용
# 실제 구현에서는 수백만 개 노드 처리가 필요해
# Contraction Hierarchies, ALT 알고리즘 등 최적화 적용
def road_navigation(road_graph, start_location, end_location):
"""
road_graph: {교차로: [(다음교차로, 거리km, 예상시간min), ...]}
"""
dist, prev = dijkstra_heap(road_graph, start_location,
n=len(road_graph))
path = reconstruct_path(prev, start_location, end_location)
# 경로 상세 정보 구성
result = {
"total_distance": dist[end_location],
"path": path,
"estimated_time": calculate_time(path, road_graph)
}
return result
# 실제 네비게이션 고려 사항:
# - 실시간 교통량 반영 → 가중치 동적 업데이트
# - 회전 제한(좌회전 금지) → 간선 확장 기법
# - 고속도로 우선 → 다중 기준 최적화
# - 수백만 노드 처리 → Bidirectional Dijkstra사례 ② OSPF 네트워크 라우팅
인터넷 라우터들이 패킷 경로를 결정하는 OSPF(Open Shortest Path First) 프로토콜은 다이크스트라 알고리즘을 직접 사용합니다.
OSPF 동작 방식:
1. 각 라우터가 링크 상태(대역폭, 지연, 비용)를 브로드캐스트
2. 모든 라우터가 동일한 링크 상태 데이터베이스 구성
3. 각 라우터가 자신을 출발점으로 다이크스트라 실행
4. 최단 경로 트리 구성 → 라우팅 테이블 생성
가중치 계산:
cost = 10^8 / bandwidth(bps)
100Mbps 링크: cost = 1
10Mbps 링크: cost = 10
1Mbps 링크: cost = 100사례 ③ 게임 AI 경로 탐색
python
# 게임 맵에서의 최단 경로 (타일 기반)
def game_pathfinding(game_map, start, goal):
"""
game_map: 2D 그리드, 0=이동가능, 1=장애물
각 타일이 노드, 인접 타일 연결이 간선
이동 비용: 평지=1, 산악=3, 수중=5 (지형에 따른 가중치)
"""
rows, cols = len(game_map), len(game_map[0])
# 2D 좌표 → 1D 인덱스 변환
def idx(r, c): return r * cols + c
n = rows * cols
graph = defaultdict(list)
# 4방향 이동 (대각선 포함하면 8방향)
directions = [(0,1),(0,-1),(1,0),(-1,0)]
terrain_cost = {0: 1, 2: 3, 3: 5} # 지형 코드별 이동 비용
for r in range(rows):
for c in range(cols):
if game_map[r][c] == 1: # 장애물 건너뜀
continue
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols:
if game_map[nr][nc] != 1: # 목적지가 장애물 아닐 때
cost = terrain_cost.get(game_map[nr][nc], 1)
graph[idx(r,c)].append((idx(nr,nc), cost))
dist, prev = dijkstra_heap(graph, idx(*start), n)
return reconstruct_path(prev, idx(*start), idx(*goal))
# 실제 게임에서는 A*를 더 많이 사용하지만,
# 유닛 여러 개의 경로를 동시에 계산할 때는
# 다이크스트라로 전체 맵 최단거리 사전 계산 후 재사용사례 ④ 코딩 테스트 실전 패턴
python
# 백준 1753 "최단경로" 유형 - 표준 다이크스트라 템플릿
import heapq
import sys
input = sys.stdin.readline
def solve():
V, E = map(int, input().split()) # 정점 수, 간선 수
K = int(input()) # 출발 정점 (1-indexed)
graph = [[] for _ in range(V + 1)]
for _ in range(E):
u, v, w = map(int, input().split())
graph[u].append((v, w)) # 방향 그래프
INF = float('inf')
dist = [INF] * (V + 1)
dist[K] = 0
heap = [(0, K)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue
for v, w in graph[u]:
nd = dist[u] + w
if nd < dist[v]:
dist[v] = nd
heapq.heappush(heap, (nd, v))
for i in range(1, V + 1):
print("INF" if dist[i] == INF else dist[i])
solve()
# ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
# 코딩 테스트 체크리스트:
# ✓ 1-indexed vs 0-indexed 확인
# ✓ 방향 vs 무방향 그래프 확인
# ✓ 최단 거리 초기값 INF 설정
# ✓ 출발 노드 dist[K] = 0
# ✓ 힙에서 꺼낼 때 d > dist[u] 체크
# ✓ 도달 불가 노드 "INF" 출력 처리
# ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━면접 모범 답변 – “다이크스트라 알고리즘을 설명해주세요”
“다이크스트라 알고리즘은 단일 출발점에서 모든 노드까지의 최단 경로를 구하는 그리디 알고리즘입니다. 핵심 아이디어는 두 가지입니다. 첫째, 매 단계에서 아직 처리하지 않은 노드 중 현재까지 발견된 최단 거리가 가장 짧은 노드를 선택합니다. 둘째, 그 노드를 경유해 인접 노드로 가는 거리를 계산해 더 짧으면 업데이트하는 완화 과정을 반복합니다. 나이브 구현은 O(V²)이지만, 우선순위 큐를 사용하면 O((V+E) log V)로 최적화됩니다. 단, 모든 간선의 가중치가 양수여야만 정확하게 동작하며, 음수 가중치가 있는 경우 벨만-포드 알고리즘을 사용해야 합니다. 실무에서는 OSPF 네트워크 라우팅, 네비게이션 경로 탐색, 게임 AI 이동 경로 계산에 핵심적으로 활용됩니다.”
결론
다이크스트라 알고리즘은 탐욕적 선택과 완화라는 두 개의 단순한 아이디어가 결합된 엘레강트한 알고리즘입니다. 나이브 구현의 O(V²)에서 우선순위 큐를 더해 O((V+E) log V)로 최적화하는 과정, 음수 가중치에서 실패하는 이유와 벨만-포드와의 선택 기준, A*와의 차이까지 — 이 흐름을 논리적으로 연결해 설명할 수 있을 때 진짜 이해한 것입니다. 오늘 구현한 코드를 직접 IDE에서 실행하고, 각 단계의 dist 배열 변화를 출력해가며 눈으로 확인해보세요. 시각화된 탐색 과정이 머릿속에 새겨지는 순간 코딩 테스트와 면접 모두에서 막힘 없이 답할 수 있게 됩니다.
답글 남기기