Dijkstra & A-Star

다익스트라 ( Dijkstra )

가중치가 있는 길 찾기 기본형

가중치 ( 거리 , 비용 )가 있는 그래프에서 시작점 → 모든 지점까지의 최단거리를 구하는 알고리즘

가장 가까운 길부터 차근차근 확정하는 방식이다.

 

 

작동 원리

네비게이션이 도로 전체를 훑어서 최단거리 지도를 만드는 과정이라고 보면 된다.

1. 출발점에서 가장 가까운 노드부터 확정한다.
2. 확정된 노드를 기준으로 주변 노드의 거리를 갱신 ( update ) 한다.
3. 다시 "가장 가까운 노드"를 뽑는다.
4. 이 과정을 반복하면 결국 모든 지점까지의 최단거리 테이블이 만들어진다.

역할 : 하나의 시작점에서 모든 노드까지의 최단 거리를 구하는 알고리즘

조건 : 간선 가중치가 음수가 아니어야 한다 ( 0 이상 )

탐색 방식 :

    └ 지금까지 발견한 거리 중에서 제일 짧은 노드를 하나씩 확정

    └ 어디가 목표인지 모른다는 느낌으로 , 사방으로 퍼져 나가며 최소 비용을 확정

 

목표 노드가 하나든 여러 개든 상관없이 전체 최단 거리 지도를 만든다

 

 

 

에이스타 ( A* , 다익스트라 + Heuristic 추가 )

목적지까지 최단 경로를 더 빨리 찾기 위한 최적화된 길찾기

Unity NavMesh 또는 2D Grid Pathfinding 에서 자주 사용된다

 

 

작동 원리

A* 는 다익스트라 방식에 휴리스틱 ( Heuristic )이라는 예상치를 더해 빠르게 목적지 방향으로 탐색하는 알고리즘

즉 , 가장 싸게 갈 수 있을 것 같은 길을 먼저 탐색한다.

역할 : 시작 노드 → 특정 목표 노드까지의 최단 경로를 찾는 알고리즘

핵심 차이 :

    └ 다익스트라는 지금까지 온 실제 거리 ( G ) 만 보고 판단한다

    └ A* 는 여기에 앞으로 남은 거리의 추정값 ( H )까지 더해서 F = G + H 로 판단한다

H ( 휴리스틱 )

    └ 목표까지 얼마나 남았을까? 대략적인 예측

    └ 예 : 2D 좌표에서 유클리드 거리 , 맨해튼 거리 등

A* 는 목표 방향으로 유망해 보이는 곳부터 집중적으로 탐색

제대로 된 휴리스틱을 쓰면 다익스트라보다 훨씬 적은 노드를 보고도 같은 최단 경로를 찾을 수 있다.

 

 

 

Dijkstra vs A - Star

공통점

• 둘 다 가중치 그래프에서 최단 경로를 찾는 알고리즘이다
• 간선 가중치가 음수가 아니면 최단 경로를 보장할 수 있다

차이점

항목	다익스트라	에이스타
목적	시작 → 모든 노드 최단거리	시작 → 특정 목표 노드 최단 경로
사용하는 값	G ( 지금까지 비용 )	G + H ( 실제 비용 + 휴리스틱 )
휴리스틱 ( H )	사용하지 않는다	사용한다
탐색 범위	사방으로 고르게 퍼진다	목표 방향으로 치우쳐 탐색한다
속도	더 많은 노드를 탐색할 수도 있다	좋은 H 사용 시 훨씬 빠르다
특수 케이스	ㅡ	H 를 항상 0 으로 두면 다익스트라와 같아진다

• 다익스트라 : 목적지가 어딘지 상관없이 시작점에서 모든 노드까지의 최단거리를 계산
• 에이스타 : 명확한 목표 지점이 반드시 있다. 목표가 어딘지 알기 때문에 H 으로 방향을 예측하면서 탐색한다.

 

 

정리

다익스트라 : 시작점에서 모든 곳까지 , 완전히 최단거리 지도를 만들어줘

에이스타 : 이 목표까지 가야 한다. 대충 방향 감 ( 휴리스틱 ) 도 있으니까 , 유망한 길부터 빠르게 찾아줘.