다익스트라 최단경로 시각화
가중치 그리드에서 최소 비용 경로를 찾는 다익스트라 알고리즘을 학습합니다
탐색★★☆
속도
1 / 1탐색 노드: 0대기열 크기: 0
그리드 크기15 x 20
가중치 유형
시작점 목표점 벽 탐색 완료 탐색 대기 최단 경로
다익스트라가 최소 거리 노드를 선택하는 과정을 관찰하세요.
다익스트라가 최소 거리 노드를 선택하는 과정을 관찰하세요.
다익스트라 알고리즘이란?
다익스트라(Dijkstra) 알고리즘은 가중치가 있는 그래프에서 한 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 1956년 에츠허르 다익스트라가 발명했으며, 네비게이션, 네트워크 라우팅, 게임 AI 등에 광범위하게 사용됩니다.
사용 방법
- 1가중치 유형을 선택하세요 — 균일(1), 랜덤(1-5), 지형(패치)
- 2그리드를 클릭/드래그하여 벽을 그리세요
- 3가중치 표시를 켜면 각 셀의 이동 비용을 볼 수 있습니다
- 4거리 표시를 켜면 시작점에서의 최단 거리를 확인합니다
- 5Dijkstra vs A* 비교 모드로 탐색 효율 차이를 확인하세요
동작 원리
- 1시작 노드의 거리를 0으로, 나머지 모든 노드의 거리를 ∞로 초기화합니다.
- 2미방문 노드 중 거리가 가장 작은 노드를 선택하는 그리디(탐욕) 전략을 사용합니다.
- 3선택된 노드의 모든 이웃에 대해 새 거리(dist[current] + weight(edge))를 계산합니다.
- 4기존 거리보다 새 거리가 작으면 갱신(Relaxation)하고, 모든 노드를 방문할 때까지 반복합니다.
실무 활용
- •네비게이션 앱의 도로 네트워크 최단 경로 탐색(Google Maps, 카카오맵)에 핵심적으로 사용됩니다.
- •네트워크 라우팅 프로토콜(OSPF)에서 패킷이 최소 비용 경로로 전달되도록 경로를 결정합니다.
- •항공 노선 최적화(가중치=비용/시간)와 물류 배송 경로 최적화에 활용됩니다.
- •소셜 네트워크에서 두 사용자 간 최단 연결 경로(촌수)를 찾는 데도 사용됩니다.
비슷한 알고리즘
- •A* vs 다익스트라 — A*는 휴리스틱으로 목표 방향을 우선 탐색하여 더 빠르지만, 다익스트라는 목적지가 없어도 모든 최단 거리를 계산합니다.
- •벨만-포드 — 음수 가중치를 허용하며 O(VE)로 더 느립니다. 다익스트라는 음수 간선이 없는 그래프에서만 사용 가능합니다.
- •플로이드-워셜 — 모든 쌍의 최단 경로를 O(V³)에 계산합니다. 다익스트라는 단일 출발점에서만 계산합니다.
학습 팁
- •다익스트라는 A*에서 h=0인 특수 케이스입니다
- •가중치가 균일하면 BFS와 동일한 결과를 보입니다
- •지형 모드에서 무거운 지역(어두운 색)을 우회하는 경로를 관찰하세요
- •A*와 비교하면 다익스트라가 더 많은 노드를 탐색하는 것을 확인할 수 있습니다
자주 묻는 질문
Q. 다익스트라와 A*의 차이는?
A. 다익스트라는 시작점에서의 실제 거리(g)만 사용합니다. A*는 g + 휴리스틱(h)을 사용해 목표 방향으로 탐색을 유도하므로 더 효율적입니다.
Q. 음수 가중치가 있으면?
A. 다익스트라는 음수 가중치를 처리할 수 없습니다. 음수 가중치가 있으면 벨만-포드(Bellman-Ford) 알고리즘을 사용해야 합니다.
Q. 시간 복잡도는?
A. 이진 힙 사용 시 O((V + E) log V)입니다. 피보나치 힙을 사용하면 O(V log V + E)로 개선됩니다.