Understanding Bidirectional Dijkstra Algorithm
Dijkstra Algorithm은 내비게이션의 길찾기 뿐만 아니라 최단거리를 찾는 알고리즘으로 잘 알려져 있다. Dijkstra Algorithm은 출발지와 목적지 사이의 최단 거리 탐색을 보장하긴 하지만 탐색 거리가 멀면 멀수록 소요되는 시간도 비례적으로 증가한다는 것이 맹점이다. 이런 문제점을 해결하기 위해 다양한 방법들이 시도 되었으며 그 중 대표적인 것이 A*와 양방향 탐색이라 할 수 있다. 이 글에서는 내비게이션 업계에서 주로 적용하고 A*알고리즘보다 최적 경로 탐색을 보장하면서 탐색시간을 거의 절반으로 줄일 수 있는 양방향 탐색(Bidirectional Dijkstra Algorithm)을 자세히 알아보고자 한다. 참고로 Dijkstra Algorithm에 대해 이해가 필요하다면…