개념과 작동 원리
그래프는 위치를 정점, 이동 가능한 관계를 간선으로 나타냅니다. 경로의 비용은 지나간 간선 또는 칸에 정한 비용을 합해 정의합니다.
너비 우선 탐색은 같은 비용의 간선에서 이동 횟수 순으로 확장합니다. 다익스트라는 현재까지의 최소 누적 비용을 기준으로 후보를 선택합니다.
관계식과 성립 조건
완화는 d(v)를 min(d(v),d(u)+w(u,v))로 갱신하는 과정입니다. 더 싼 경로를 찾으면 거리와 이전 위치 정보를 함께 바꿉니다.
다익스트라의 표준 확정 절차는 음수 가중치가 없다는 조건을 사용합니다. 실험은 상하좌우 이동과 양수 비용이며 대각선이나 실제 도로 제약은 생략합니다.
가상 실험에서 읽을 변화
너비 우선 탐색은 칸 수를, 다익스트라는 비용 합을 최소로 해요.
상하좌우 이동만 허용하고 비용은 양수예요. 벽 배치와 출발·도착은 재현 가능한 프리셋으로 바꿔요.
핵심 관계와 기호
d(v) = min[d(u) + w(u,v)]
| 기호 | 뜻 | 단위 |
|---|---|---|
| d(v) | 출발점에서 v까지의 현재 거리 추정 | 비용 |
| w(u,v) | u에서 v로 이동하는 비용 | 비용 |
예시로 확인하기
모든 칸 비용이 같으면 두 방식의 최단 거리는?
같아요 · 너비 우선 탐색은 칸 수를, 다익스트라는 비용 합을 최소로 해요.
자주 헷갈리는 점
- 너비 우선 탐색이 가중치가 서로 다른 모든 그래프에서 비용 합까지 최소로 만드는 것은 아닙니다.