다익스트라 알고리즘 (Dijkstra’s Algorithm)

다익스트라 알고리즘이란

다익스트라 알고리즘은 가중치가 있는 그래프에서 하나의 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이다. 탐욕적 방법(Greedy)을 사용하며, 우선순위 큐를 활용하여 현재까지 알려진 최단 거리가 가장 짧은 정점을 선택하며 최단 경로를 갱신해 나간다.

알고리즘 시각화

동작 예시

아래와 같은 그래프가 주어졌을 때 다익스트라 알고리즘의 동작 과정을 살펴보자. (시작 정점: A)


     2     3
  A --- B --- D
  |   /       |
1 |  / 2      | 1
  | /         |
  C --------- E
        4

간선 목록:

A-B(2), A-C(1)
B-C(2), B-D(3)
C-E(4)
D-E(1)

초기 상태

정점	거리	이전 정점
A	0	-
B	∞	-
C	∞	-
D	∞	-
E	∞	-

우선순위 큐: [(A, 0)]

1단계: A 방문

A의 인접 정점 B, C의 거리를 갱신

정점	거리	이전 정점
A	0	-
B	2	A
C	1	A
D	∞	-
E	∞	-

우선순위 큐: [(C, 1), (B, 2)]

2단계: C 방문 (최소 거리)

C의 인접 정점 B, E의 거리를 확인

B: 1 + 2 = 3 > 2 (기존 값 유지)
E: 1 + 4 = 5 < ∞ (갱신)

정점	거리	이전 정점
A	0	-
B	2	A
C	1	A
D	∞	-
E	5	C

우선순위 큐: [(B, 2), (E, 5)]

3단계: B 방문

B의 인접 정점 C, D의 거리를 갱신

정점	거리	이전 정점
A	0	-
B	2	A
C	1	A
D	5	B
E	5	C

우선순위 큐: [(D, 5), (E, 5)]

4단계: D 방문

D의 인접 정점 E의 거리를 확인

E: 5 + 1 = 6 > 5 (기존 값 유지, 갱신 없음)

정점	거리	이전 정점
A	0	-
B	2	A
C	1	A
D	5	B
E	5	C

우선순위 큐: [(E, 5)]

5단계: E 방문

모든 정점 방문 완료

최종 결과

정점	최단 거리	경로
A	0	A
B	2	A → B
C	1	A → C
D	5	A → B → D
E	5	A → C → E

복잡도

구분	복잡도	설명
시간 복잡도	O(E log V)	- 우선순위 큐 삽입/추출: O(E log V)
공간 복잡도	O(V + E)	- 그래프 표현: O(V + E) - 거리 배열: O(V) - 우선순위 큐: O(V)

장단점

장점	단점
빠른 속도 - O(E log V)로 효율적 - 대부분의 최단 경로 문제에 적합	음수 가중치 불가 - 음수 간선이 있으면 오작동 - 벨만-포드 알고리즘 사용 필요
정확한 최단 경로 - 탐욕적 선택으로 최적해 보장 - 경로 추적 가능	단일 출발점만 가능 - 한 번에 하나의 시작 정점만 처리 - 모든 쌍은 플로이드-워셜 사용
우선순위 큐 활용 - 효율적인 자료구조 사용 - 구현이 비교적 간단	초기 거리 설정 - ∞ 표현 주의 (큰 값 사용) - 오버플로우 방지 필요

주의사항

음수 가중치 간선이 있으면 사용 불가 (벨만-포드 사용)
우선순위 큐는 최소 힙으로 구현 (거리가 짧은 것부터 추출)
방문 처리를 통해 중복 방문 방지 (효율성 향상)
무한대 표현: 충분히 큰 값 사용 (Integer.MAX_VALUE 등)
경로 복원: 이전 정점 배열을 별도로 저장
우선순위 큐 업데이트: 거리 갱신 시 새로운 엔트리 추가 (기존 엔트리는 방문 체크로 무시)

구현 팁

우선순위 큐: PriorityQueue<int[]> 사용, [정점, 거리] 형태
거리 초기화: Arrays.fill(dist, Integer.MAX_VALUE)
거리 갱신: if (dist[u] + w < dist[v]) 조건 확인
경로 추적: int[] prev 배열로 이전 정점 저장
방문 체크: 우선순위 큐에서 꺼낸 후 즉시 확인