정의
칭화대 연구팀이 제안한 재귀적 부분 정렬(Recursive Partial Ordering)은 Dijkstra 알고리즘의 41년 된 시간 복잡도 한계를 깨기 위해, 모든 노드를 완전 정렬하지 않고 최단 경로를 찾는 방법이다. Bellman-Ford 알고리즘의 논리를 결합하여 O(m log^(2/3) n)의 시간 복잡도를 달성하며, 이는 기존의 O(m + n log n)보다 이론적으로 우월하다.
핵심 속성
- 문제 대상: Single-Source Shortest Path (SSSP) — 하나의 출발점에서 모든 노드까지의 최단 경로
- 기존 최적 복잡도: O(m + n log n) (Dijkstra with Fibonacci heap, 1984년 이후)
- 새로운 복잡도: O(m log^(2/3) n)
- 핵심 기법: 재귀적 부분 정렬 — 전체 노드를 거리 순으로 완전 정렬하지 않고, 부분적인 순서 관계만 유지하여 우선순위 큐의 정렬 비용 절감
- 파생 배경: Bellman-Ford 알고리즘의 완화(relaxation) 과정에서 발생하는 구조적 특성 활용
- 적용 환경: 대규모 희소 그래프(예: 웹 그래프, 글로벌 물류 네트워크)에서 특히 유의미한 성능 향상
관계
- 20260605-sssp-recursive-partial-ordering — 자기 참조 (개념 정의)
- 20260513-dijkstra-algorithm — 대조: 기존 최적 알고리즘에서 sorting barrier를 깸
- bellman-ford-algorithm — 연장: 부분 정렬 로직의 기반이 된 알고리즘
- sorting-barrier — 상위개념: 알고리즘 복잡도 이론의 한계 개념
- tsinghua-university-research-team — entity: 연구 수행 주체
인용
“They proved that Dijkstra is not optimal. By combining the logic of the Bellman-Ford algorithm with a revolutionary ‘recursive partial ordering’ method, they figured out how to find the path without fully sorting the nodes.”