41년만에 새로운 최단경로 알고리즘을 발견
(arxiv.org)중국 칭화대(Tsinghua University) 연구진이 스탠포드 대학과 협력해, 전통적 최단 경로(single-source shortest path, SSSP) 문제에 대한 계산 복잡도 측면에서 큰 발전을 이루었음. 이 연구는 2025년 STOC 학회에서 Best Paper 상을 수상.
전통적으로 많이 쓰이는 방법이 디익스트라(Dijkstra)의 알고리즘으로, 시간 복잡도가 O(m + n log n) (n = 노드 수, m = 간선 수) 형태임.
log n항은 우선순위 큐(priority queue)나 정렬(sorting)과 관련된 부분으로, 지난 40년간 이 부분을 뛰어넘는 개선이 없었음.
새로운 알고리즘은 시간 복잡도를 O(m · log^(2/3) n) 으로 줄였음.
log^(2/3) n 은 log n 보다 느리게 증가하므로 (즉 log n 보다 작게 늘어남), 노드 수가 매우 클 경우 차이가 커짐.
2000년대 말에 차량 네비게이션 소프트웨어 업체에서 일하면서 경로 탐색 모듈을 개발하던 추억(?)이 떠오르네요.
Dijkstra는 네비게이션 경로 탐색엔 너무 느려서 안 쓰고 휴리스틱 개선 버전인 A*(A Star) 검색을 사용하죠. 찾아보니 A*는 SSSP가 아니라 SPSP(Single-Pair Shortest Path) 알고리즘이군요.