최단경로 탐색에서 Dijkstra와 A*를 선택하는 기준

최소 비용 경로를 찾는 문제

라우팅, 지도, 로보틱스, 게임 AI에서는 두 지점 사이를 연결하는 경로 중 누적 비용이 가장 낮은 선택지를 찾아야 한다. 최단경로는 가중 그래프에서 시작 노드부터 목표 노드까지의 비용 합을 최소화하는 경로를 탐색하는 문제다.

대표적인 해법은 Dijkstra와 A다. Dijkstra는 모든 간선 가중치가 음수가 아닐 때 우선순위 큐를 사용해 최단 비용 정점을 차례로 확정한다. A는 f(n)=g(n)+h(n) 평가 함수에 휴리스틱 h(n)을 더해 목표에 가까운 후보를 먼저 탐색한다. h(n)이 허용적(admissible)이고 일관적(consistent)이면 A*도 최적 경로를 보장한다.

그래프 모델과 탐색 상태를 잡는 방법

희소 그래프는 인접 리스트로 표현하는 편이 메모리 사용과 갱신 측면에서 유리하다. 가중치는 비음수 실수 또는 정수로 표준화하고, 음수 가중치가 있다면 Bellman-Ford 같은 대체 알고리즘을 고려한다.

Dijkstra는 누적 비용 g(n)을 기준으로 최소 힙을 정렬한다. 정점이 확정될 때 최단거리 불변성이 유지된다. A*는 f(n)=g(n)+h(n)을 우선순위로 사용하며, 탐색 대기 상태인 Open set과 방문 확정 상태인 Closed set을 관리한다.

A의 휴리스틱은 탐색량을 좌우한다. 허용성은 h(n) ≤ 실제 잔여 비용을 만족하는 성질이고, 일관성은 h(n) ≤ c(n,m)+h(m)을 만족하는 성질이다. 일관성이 있으면 이미 닫힌 노드를 다시 여는 처리가 필요하지 않다. 유클리드 거리, 맨해튼 거리, 지형 가중 휴리스틱처럼 도메인에 맞는 함수를 선택한다. h=0이면 A는 Dijkstra와 동등하게 동작한다.

목표 정점을 꺼내는 시점에 탐색을 끝내는 조기 종료를 적용할 수 있다. 모든 정점의 완화를 마칠 필요는 없다. 최종 경로는 각 노드에 기록한 parent 포인터를 역추적해 복원한다. Dijkstra에서는 비음수 가중치 조건을 지키고, 가중치 0 순환에 따른 무한 루프를 막는 로직도 필요하다.

알고리즘 선택 기준

항목	Dijkstra	A*
성능	O(E log V), 탐색 범위가 넓음	O(E log V) 이론 유사, 좋은 h로 정점 확장 수 크게 감소
확장성	대규모 그래프에서 안정적, 전역 탐색 적합	도메인 지식 포함 시 대규모에서도 고성능, 휴리스틱 준비 필요
일관성	비음수 가중치에서 최적성 확정	허용·일관 휴리스틱에서 최적성 보장
안정성	휴리스틱 불필요, 결과 예측 가능	휴리스틱 품질 민감, 부적절 h 시 성능 저하 가능
운영 편의	구현 단순, 튜닝 포인트 적음	휴리스틱 설계·검증 필요, 도메인 의존성 존재

탐색과 경로 복원의 흐름

⤢✕

경로 탐색이 쓰이는 환경

지도 라우팅에서는 도로 네트워크에 A*와 유클리드 또는 대수적 거리 휴리스틱을 적용하고, 일방통행과 속도제한을 가중치로 모델링한다. 대규모 서비스는 Contraction Hierarchies와 ALT landmarks 같은 전처리를 이용해 지연시간을 줄일 수 있다.

게임 AI와 로보틱스의 격자 지도에서는 맨해튼 거리나 대각선 비용 휴리스틱을 쓰고, 장애물과 지형 비용을 반영한다. 환경이 계속 바뀌면 증분형 A인 D Lite로 재계획 비용을 줄이는 방식을 고려한다.

네트워크와 시스템 라우팅에서는 지연, 손실률, 대역폭 역수를 가중치로 두고 QoS 정책에 따라 경로를 선택한다. 장애가 발생했을 때 대체 경로를 빠르게 탐색하는 구조는 이중화 설계와 함께 다뤄야 한다.

성능과 운영에 미치는 영향

동일 그래프에서 적절한 휴리스틱을 적용한 A*는 Dijkstra와 비교해 정점 확장 수를 수 배 이상 줄일 수 있다. 경험적 범위는 3배~50배이며, 도메인과 휴리스틱 품질에 따라 달라진다. ALT 또는 CH 전처리를 병행하면 쿼리 지연을 밀리초 단위로 달성할 수 있지만, 메모리와 전처리 시간의 교환관계가 따른다.

허용적이고 일관적인 휴리스틱은 최적 경로와 결과 재현성을 뒷받침한다. 음수 가중치를 차단하고 입력을 검증하며 조기 종료를 적용하면 운영 장애를 예방하는 데 도움이 된다. CPU 시간과 메모리 사용량을 줄이면 인프라 비용과 스케일아웃 노드 수를 낮출 수 있고, 캐시와 전처리의 재사용은 반복 쿼리 비용을 추가로 줄인다.

운영 환경에서 확인할 설계 항목

인접 리스트와 최소 힙(heapq/priority_queue)을 기본 구조로 두고, 대규모 그래프에서는 ID 압축과 메모리 풀을 적용한다. 키 감소(decrease-key)를 지원하지 않는 힙은 재삽입 전략으로 대체하고 lazy deletion으로 성능을 유지할 수 있다.

휴리스틱은 격자 4/8방에는 맨해튼 거리, 연속 좌표에는 유클리드 거리, 도로망에는 대칭 사다리꼴 거리처럼 문제 적합성을 우선한다. 무작위로 뽑은 간선에서 h(u) ≤ w(u,v)+h(v)를 점검하는 방식으로 허용성과 일관성 검증 절차를 마련한다.

탐색 폭을 줄여야 한다면 Bidirectional Dijkstra/A*, Multi-target 탐색을 검토한다. ALT(랜드마크+삼각부등식), Contraction Hierarchies, HPA도 전처리 기반 가속기로 활용할 수 있다. 동적 가중치 환경에는 D Lite 또는 경계 상향식 Anytime Repairing A*를 적용한다.

입력 단계에서는 음수, NaN, Infinity 가중치를 차단한다. 경로가 없을 때는 원인 코드와 진단 정보를 반환하고, 가중치 0 순환 감지와 확장 제한을 둔다. 최대 확장 노드 수와 시간 제한 역시 탐색 서비스의 보호 장치가 된다.