Dijkstra 알고리즘은 41년 동안 이론적으로 ‘최적’이라고 증명된 상태였다. 심지어 Robert Tarjan이 2023년에 이 한계가 절대적임을 공식 수상과 함께 입증했을 정도다. 그런데 칭화대 연구팀은 정확히 그 증명의 전제 — ‘정렬이 반드시 필요하다’ — 를 뒤집음으로써 더 나은 알고리즘을 내놓았다. 이 사건은 과학에서 ‘최적’이라는 단어가 얼마나 조건적이고 일시적인지를 보여준다.
근거
Tarjan의 증명은 Dijkstra가 정렬 기반 우선순위 큐를 사용한다는 가정 하에 내려졌다. 연구팀은 ‘정렬하지 않는다’는 전략을 택함으로써 그 증명의 적용 범위 자체를 무효화했다. 한계는 알고리즘 자체가 아니라, 문제를 푸는 방식에 대한 우리의 가정에 있었던 것이다.
“For four decades, the greatest minds in algorithms believed this limit was absolute. Last year, even the legendary Robert Tarjan won an award proving Dijkstra was ‘optimally efficient’ at sorting distances. Tsinghua’s answer? Stop sorting.”
연결된 생각
- 20260605-sssp-recursive-partial-ordering — 이 개념이 구체적으로 어떤 방식으로 가정을 전환했는지
- 과학적 패러다임 전환의 조건 — Kuhn의 구조와 이 사례의 유사성