Get to know the Contraction Hierarchy
앞서 길찾기 알고리즘 관련해서 2개의 알고리즘(Dijkstra, BidirectionalDijkstra)에 대해 살펴봤다. 컴퓨터를 활용하여 길을 찾아가는 알고리즘의 목적은 크게 최적의 경로를 최대한 빨리 찾아내는 것이라 할 수 있다. 이론적으로 이들 알고리즘은 최적의 경로를 찾아주는 것을 보장하지만 최대한 빨리 찾는 것에는 한계를 드러내고 있다. 앞에서 설명한 BidirectionalDijkstra 알고리즘도 이런 맥락에서 탐색속도를 개선하기 위한 하나의 방법으로 볼 수 있다. 이처럼 Dijkstra Algorithm의 탐색 속도는 탐색공간 크기에 종속적일 수 밖에 없으며 나아가 길찾기가 한 국가를 넘어 글로벌 규모로 확대해 나간다면 탐색 속도는 서비스 경쟁력을 유지에 중요한…