모든 최단 경로 알고리즘 교과서는 Dijkstra를 가르칠 때 ‘정렬’을 필수 불가결한 과정으로 설명한다. 칭화대 연구팀은 그 프레임 자체를 의심했다. Bellman-Ford의 완화 과정과 결합된 ‘재귀적 부분 정렬’은 전체 정렬 없이도 올바른 경로를 찾을 수 있음을 증명한다. 이는 문제를 바라보는 관점을 바꾸면 기존에 불가능해 보였던 해결책이 열릴 수 있다는 강력한 사례다.
근거
연구팀은 SSSP 문제를 ‘거리 순으로 모든 노드를 정렬해야만 푼다’는 전제를 버리고, ‘일부 노드의 상대적 순서만 알아도 경로를 확정할 수 있다’는 발상으로 전환했다. 이 전환은 기존 증명이 사용한 정렬 하한을 회피하는 새로운 복잡도 클래스를 열었다.
“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.”
연결된 생각
- 20260605-sssp-recursive-partial-ordering — 재귀적 부분 정렬의 구체적 정의
- 가정을 깨는 역발상의 사례 — 과학사에서 유사한 패턴 (예: 비유클리드 기하학)