정의
칭화대 연구팀이 발표한 단일 출발점 최단경로(Single-Source Shortest Path, SSSP) 알고리즘. 1984년 이래 40년간 절대적이라 여겨진 다익스트라의 “정렬 장벽(sorting barrier)“을 깨고, 결정론적(deterministic) 시간 복잡도 개선을 달성했다.
핵심 속성
- 새로운 시간 복잡도: O(m log^(2/3) n) — 기존 O(m + n log n) 한계 돌파
- 돌파 원리: 벨만-포드 알고리즘 로직 + “재귀적 부분 순서(recursive partial ordering)” 결합. 모든 노드를 완전 정렬하지 않고도 최단 경로 발견
- 이전 정설 부정: 2024년 Robert Tarjan이 “다익스트라는 정렬 거리 측면에서 최적 효율적”임을 증명해 상까지 받았으나, 칭화팀은 “정렬을 멈춰라”로 응답
- 실용 영역: 대규모 희소 그래프(웹, 글로벌 로지스틱스)에서 종전보다 유의미하게 빠른 라우팅 가능
- 응용 도메인: Google Maps, 항공편 예약, 인터넷 패킷 라우팅 등 다익스트라 기반 인프라 전반
- 이론적 의의: 40년간 “절대적”이라 믿었던 한계가 깨졌다는 사실 자체. 다른 “불가능”한 속도 한계도 재검토 가능성
관계
- 20260513-dijkstra-algorithm — 대조: 41년간 정설이었던 기존 알고리즘
- 20260515-forward-algorithm — 연장: 그래프/시퀀스 알고리즘의 인접 영역
인용
For four decades, the greatest minds in algorithms believed this limit was absolute. Tsinghua’s answer? Stop sorting.