알고리즘AlgorithmGraphDijkstraShortest PathGreedy
다익스트라 최단 경로
단일 출발지에서 다른 모든 노드로 가는 최단 경로 탐색
시각화 로드 중...
알고리즘 복잡도
최선O((V+E) log V)
평균O((V+E) log V)
최악O((V+E) log V)
공간O(V + E)
개요
Algorithm Overview
다익스트라(Dijkstra) 알고리즘은 가중치 그래프 상에서 특정 시작 노드로부터 다른 모든 노드까지의 최단 거리를 구하는 단일 출발점 최단 경로 알고리즘입니다. 매 단계마다 미방문 노드 중 누적 거리가 가장 짧은 노드를 탐욕적(Greedy)으로 확정합니다.
01
다익스트라의 핵심 전제 및 완화 기법
- 비음수 가중치 전제: 음의 가중치를 가지는 간선이 없을 때만 올바르게 동작합니다 (음수 간선 존재 시 벨만-포드 알고리즘 필요).
- 거리 테이블 완화 (Edge Relaxation): 현재 선택된 노드 $u$를 거쳐 인접 노드 $v$로 가는 새로운 비용이 기존에 기록된 최단 거리보다 작으면 테이블을 갱신합니다.
- 점화 수식:
dist[v] = min(dist[v], dist[u] + weight(u, v))
02
알고리즘 동작 4단계 흐름
- 최단 거리 테이블 초기화: 출발 노드의 거리는 0으로 설정하고, 나머지 모든 노드의 최단 거리는 무한대(
INF)로 초기화합니다. - 최소 거리 노드 선택: 미방문 노드 중 현재 출발지로부터의 최단 거리가 가장 짧은 노드를 우선순위 큐(Min Heap)에서 추출합니다.
- 인접 노드 완화 (Relaxation): 선택된 노드의 인접 노드들을 순회하며, 해당 노드를 거쳐 갈 때의 누적 거리를 계산하여 테이블을 갱신합니다.
- 방문 확정 및 반복: 선택 노드를 방문 완료 처리하고, 모든 노드가 방문될 때까지 2~3단계를 반복하여 최종 최단 경로 트리를 완성합니다.
입력을 따라가는 실행 예제
시작 A에서 B(가중치 4), C(가중치 1), C에서 B(가중치 2)인 그래프를 보겠습니다. 초기 거리는 A=0, B=∞, C=∞이고, A를 처리하면 B=4, C=1입니다. 다음 C에서 B를 완화하면 B=3으로 바뀝니다. 따라서 A→C→B 경로 비용 3이 직접 간선 비용 4보다 짧습니다.
학습 목표
- 간선 완화에 따른 거리 테이블 변경을 설명할 수 있다.
자주 하는 오해
- 우선순위 큐에서 꺼낸 항목이 오래된 거리라면 최신 거리 테이블과 비교해 건너뛰어야 합니다. 음수 간선에는 일반적인 다익스트라를 적용할 수 없습니다.
핵심 정리
- 우선순위 큐 구현에서는 보통 O((V+E) log V)로 설명하며 도달 불가능한 정점은 거리가 무한대로 남습니다.
학습 확인
핵심 단계
- 1
출발 노드를 설정하고 최단 거리 테이블을 초기화 (출발지는 0, 나머지는 무한대)
- 2
미방문 노드 중 최단 거리가 가장 짧은 노드를 선택하고 방문 처리
- 3
선택한 노드를 거쳐 갈 수 있는 인접 노드의 거리를 계산하여 기존 거리보다 작으면 테이블 갱신
- 4
모든 노드를 방문하거나 미방문 노드의 최소 거리가 무한대가 될 때까지 반복
핵심 개념 및 실무 적용 분야
✓네트워크 OSPF 라우팅 프로토콜에서의 최단 경로 패킷 전송
✓실시간 GPS 내비게이션 및 지도 길찾기 경로 최적화
✓게임 내 NPC의 목표물 추적 및 최단 이동 경로 계산
참고 자료
개념과 기술 규격을 추가로 확인할 수 있는 외부 자료입니다. 시각화는 교육 목적에 맞게 일부 절차를 단순화할 수 있습니다.