재귀적 부분 순서화 기반 최단 경로 알고리즘

정의

다익스트라 알고리즘이 가졌던 ‘정렬 장벽(Sorting Barrier)‘을 극복하고, 노드를 완전히 정렬하지 않는 ‘재귀적 부분 순서화’ 방식을 통해 단일 출발지 최단 경로(SSSP)를 찾는 혁신적인 알고리즘이다.

핵심 속성

• 시간 복잡도: $O(m{\log }^{2/3}n)$ — 기존 다익스트라의 $O(m+n\log n)$ 한계를 41년 만에 경신함.
• 알고리즘 결합: bellman-ford-algorithm의 논리와 새로운 ‘재귀적 부분 순서화(Recursive Partial Ordering)’ 메커니즘을 결합.
• 최적성: 다익스트라가 ‘정렬 기반’으로는 최적일지라도, SSSP 문제 자체에 대해서는 최적이 아님을 입증함.
• 대상: 웹 그래프나 글로벌 물류망과 같은 거대 희소 그래프(Massive Sparse Graphs)에서 비약적인 성능 향상을 보임.

관계

• 20260513-dijkstra-algorithm — 대조: 정렬 장벽을 가진 기존의 표준 알고리즘.
• bellman-ford-algorithm — 연장: 본 알고리즘의 논리적 토대가 된 기존 알고리즘.
• SSSP-Problem — 상위개념: 단일 출발지에서 모든 정점까지의 최단 거리를 구하는 문제.

인용

“Tsinghua’s answer? Stop sorting. The world’s most settled problem is suddenly wide open again.”

출처

클리핑 · x.com