다익스트라 알고리즘
시작점에서 목표까지 가장 싼 길을 찾습니다. 우선순위 큐에서 기다리는 가장 싼 곳을 항상 먼저 꺼내므로, 비용이 시작점에서 홍수처럼 퍼져 나갑니다.
- 시간 O((V + E) log V)
- 메모리 O(V)
- 우선순위 큐 사용
용어 설명
- 비용: 한 번 이동하는 값. 미로에서는 땅 1, 진흙 3, 물 9이고, 그래프에서는 간선에 적힌 수입니다.
- 우선순위 큐: 먼저 온 순서가 아니라 가장 싼 것이 먼저 나가는 대기열.
- 추정치(h): 남은 비용에 대한 예상. 추정치가 결코 너무 크지 않을 때만 A*가 정확합니다.
- 간선 완화: 현재 장소를 거치면 이웃의 비용이 낮아지는지 확인하고, 낮아지면 그 값을 받아들이는 것.
0 / 294 단계
- 큐에 있음
- 현재
- 완료
- 가장 싼 길
- 땅 · 1
- 진흙 · 3
- 물 · 9
- 벽
발견: A1에서 비용 0으로 시작합니다. 큐에 있는 유일한 칸입니다.
스페이스바: 재생 또는 일시정지. 좌우 화살표 키: 단계 이동. Home과 End 키: 처음과 끝으로 이동.
해 보세요: ‘늪’을 고르세요. 가장 싼 길은 진흙을 빙 돌아갑니다. 직선보다 이동이 두 배지만 그래도 더 쌉니다(36 대 34).
작동 방식
모든 곳에 비용을 매깁니다. 시작점은 0, 나머지는 무한대입니다. 다익스트라는 도달한 곳을 우선순위 큐에 두고 항상 가장 싼 곳을 꺼냅니다. 그러면 그 비용은 확정됩니다. 다른 어떤 길도 적어도 그만큼 비싼 곳을 지나야 하기 때문입니다. 이어서 이웃을 하나씩 봅니다. 방금 꺼낸 곳을 거쳐 가는 것이 이웃의 지금까지 비용보다 싸면, 이웃은 새 비용을 받고 어디서 왔는지 기억합니다. 목표를 꺼내면 이 기록을 따라 가장 싼 길로 되돌아갈 수 있습니다.
언제 쓰면 좋을까
이동 비용이 서로 다르고 0보다 작은 비용이 없을 때 쓰세요. 도로 지도와 내비게이션, 네트워크 라우팅, 가장 싼 항공 환승 등입니다. 모든 이동 비용이 같다면 BFS가 같은 답을 더 간단히 냅니다. 음수 비용이 있으면 다익스트라가 틀릴 수 있으니 벨만–포드를 쓰세요.