40년 넘게 알고리즘 학계는 ‘최단 경로를 찾으려면 노드를 거리순으로 정렬해야 한다’는 전제를 절대적인 진리로 받아들여 왔다. 하지만 칭화대 연구팀은 이 ‘정렬’이라는 과정 자체가 성능의 병목임을 간파하고, 정렬을 포기함으로써 오히려 더 빠른 경로를 찾아냈다. 이는 기술적인 최적화를 넘어, 우리가 당연하게 여기는 시스템의 근본 전제를 의심할 때 비로소 거대한 도약이 가능함을 시사한다.
근거
전설적인 알고리즘 학자 로버트 타잔(Robert Tarjan)조차 작년에 다익스트라 알고리즘이 ‘정렬에 있어 최적의 효율성’을 가졌음을 증명하며 상을 받았다. 이는 전문가들조차 ‘최단 경로 = 정렬’이라는 프레임 안에 갇혀 있었음을 보여준다.
“For four decades, the greatest minds in algorithms believed this limit was absolute… Tsinghua’s answer? Stop sorting.”
연결된 생각
- 20260605-recursive-partial-ordering-sssp — 정렬을 대체한 구체적인 기술적 메커니즘.
- 20260605-massive-graph-routing-evolution — 이러한 발상의 전환이 실세계에 미칠 영향.