Dijkstra와 A* 최단 경로

본 블로그 작성 글들은, 강의를 목표로 하고 제작되었습니다. 또한 작성된 글의 정보도 틀렸을 수 있으니, 주의해주세요.

타일마다 이동 비용이 다르면 단순 BFS만으로 가장 싼 경로를 보장할 수 없다. 이때 Dijkstra와 A* 같은 최단 경로 알고리즘을 사용한다.

Dijkstra

시작점에서 현재까지 누적 비용이 가장 작은 정점을 먼저 확장한다.

새 비용 = 현재까지 비용 + 다음 간선 비용

새 비용이 기존 기록보다 작으면
거리와 이전 정점을 갱신한다.

Priority Queue를 사용하면 일반적으로 O((V + E) log V) 정도로 구현할 수 있다. 음수 간선이 있으면 이미 확정한 최단 거리가 다시 줄어들 수 있으므로 기본 Dijkstra를 사용하면 안 된다.

A*

A*는 시작점에서 온 실제 비용 g와 목표까지의 예상 비용 h를 더해서 우선순위를 정한다.

f(n) = g(n) + h(n)

격자에서는 Manhattan Distance나 Euclidean Distance를 Heuristic으로 사용할 수 있다. 육각 그리드에는 육각 좌표에 맞는 거리 함수를 사용해야 한다.

예상 비용이 실제 남은 최저 비용을 과대평가하지 않으면 최단 경로를 보장할 수 있다. Heuristic이 0이면 A*는 Dijkstra처럼 동작한다.

어느 것을 사용할까?

한 시작점에서 여러 목적지 비용 필요: Dijkstra
한 목적지까지 빠르게 탐색: A*
모든 간선 비용이 동일: BFS

경로 탐색 성능은 알고리즘 이름만으로 결정되지 않는다. 이웃 생성 비용, 장애물 표현, Priority Queue, Heuristic 품질도 함께 확인해야 한다.