41년만에 새로운 최단경로 알고리즘을 발견

(arxiv.org)

30P by pjy6076 16시간전 | ★ favorite | 댓글 13개

중국 칭화대(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 보다 작게 늘어남), 노드 수가 매우 클 경우 차이가 커짐.