가장 작은 비용이, 다음 길이 된다.
DijkstraPATH
NETWORK
03 / 20
DVERSE CITY / SECTOR 07
LN 4
dist[start] = 0; open.set(start, 0);현재 정점탐색 대기방문 완료선택 경로
방문한 정점·칸00
검사한 간선00
실행 진행률0%
dijkstra.js
JavaScript
Ln 4, 실행 중인 핵심 연산코드 줄을 눌러 이동
g0
h0
f0
001
INSPECT LINE 4
A의 거리를 0으로 설정
나머지 거리는 ∞입니다. 힙은 누적 비용이 작은 정점을 먼저 꺼냅니다.
001 / 142
MIN HEAP · 누적 비용 g 순서1
00A : 0
BEHIND THE ALGORITHM
다익스트라, 이렇게 생각하면 쉬워요.
지금까지 발견한 가장 저렴한 정점을 꺼내고, 이웃으로 가는 더 좋은 경로가 있는지 확인합니다.
더 짧은 거리를 발견해 값을 고치는 것이 완화(relaxation)입니다. 목표를 발견했을 때가 아니라 최소 힙에서 꺼냈을 때 확정합니다.
어디에 쓰일까요 길 찾기 · 네트워크 라우팅 · 최소 비용
TIME COMPLEXITYO((V + E) log V)
AUXILIARY SPACEO(V)
감소 키를 지원하는 이진 최소 힙. 음수 가중치가 없는 그래프에서 동작합니다.
같은 지도, 다른 탐색
현재 지도의 완료 결과입니다. 방문 수는 지도에 따라 같을 수도 있습니다.
코드와 그림은 어떻게 연결되나요?
각 알고리즘이 실제로 계산한 실행 기록을 순서대로 재생합니다. 한 단계는 코드의 핵심 연산에 대응하며, 큐·스택·변수와 그림은 같은 기록을 사용합니다. 화면의 JavaScript는 그 핵심 로직입니다. 입력 준비와 보조 함수의 구현은 화면에서 생략했습니다. 아래에서 각 함수의 역할을 확인할 수 있습니다. 복잡도는 애니메이션용 기록 복사를 제외한 알고리즘 기준입니다.
- pathTo(parent, goal)
- 목표부터 부모를 따라가 시작점까지의 경로를 복원합니다.
- MinHeap · UnionFind
- 최소 힙은 정점별 우선순위 갱신과 최솟값 추출을, Union-Find는 대표 찾기와 그룹 합치기를 제공합니다.
- neighbors · availableColumns · robot
- 이동 가능한 이웃, 사용하지 않은 열 목록, 이동·회전·청소를 하는 로봇 인터페이스입니다.
KEEP EXPLORING
다음엔 어떤 흐름을 따라갈까요?
20개의 알고리즘, 서로 다른 문제를 푸는 20가지 움직임.