(퍼온 글) 다이크스트라를 넘어서: 70년의 컴퓨터 과학을 새롭게 쓴 새로운 알고리즘
Move Over Dijkstra: The New Algorithm That Just Rewrote 70 Years of Computer Science
글쓴이 : The Latency Gambler
글 : Move Over Dijkstra: The New Algorithm That Just Rewrote 70 Years of Computer Science | by The Latency Gambler | Aug, 2025 | Medium
[아래는 제가 요약한 것입니다]
거의 70년 동안 다익스트라 알고리즘은 그래프에서 최단 경로를 찾는 황금률로 군림해 왔습니다. 1956년 암스테르담의 한 카페에서 20분간의 두뇌 훈련으로 탄생한 에츠게르 다익스트라의 알고리즘은 GPS 내비게이션부터 네트워크 라우팅 프로토콜에 이르기까지 모든 것의 근간이 되어 왔습니다. 하지만 그 시대는 이제 끝났습니다.
칭화대학교 란 단(Ran Duan)이 이끄는 연구팀은 많은 사람들이 불가능하다고 여겼던 것을 달성했습니다. 바로 40년 동안 최단 경로 알고리즘을 제한해 온 근본적인 "정렬 장벽"을 허물었다는 것입니다. 단일 소스 최단 경로에 대한 그들의 새로운 결정론적 O(m log^(2/3) n) 시간 알고리즘은 알고리즘의 한계에 대한 교과서적 가정에 도전하는 획기적인 발견입니다.
Duan의 획기적인 발견은 반직관적인 깨달음에서 비롯되었습니다. 정렬을 아예 하지 않는다면 어떨까요?
새로운 알고리즘은 Dijkstra의 정렬 방식을 완전히 폐기합니다. 항상 가장 가까운 정점을 선택하는 대신, 정교한 클러스터링 기법과 더 느린 Bellman-Ford 알고리즘을 선택적으로 적용하여 여러 최단 경로에 있는 “영향력 있는 노드” 정점을 식별합니다.
가장 중요한 통찰력은 근처 정점을 클러스터링하고 각 클러스터의 대표를 처리함으로써 알고리즘이 기존 접근 방식의 제한 요소인 값비싼 정렬 작업을 피할 수 있다는 것입니다.
Graph Size (n) Dijkstra New Algorithm Speedup
1,000 13,816 8,660 1.6x
10,000 151,294 75,858 2.0x
100,000 1,660,964 676,694 2.5x
1,000,000 18,420,699 6,095,885 3.0x
실제 적용 사례
이 획기적인 기술은 여러 분야에 걸쳐 즉각적인 적용이 가능합니다.
네트워크 라우팅: 인터넷 백본 라우터는 경로를 더욱 효율적으로 계산하여 데이터 전송 지연 시간을 단축할 수 있습니다.
GPS 내비게이션: 지도 애플리케이션은 특히 수백만 개의 도로 구간이 있는 밀집된 도시 네트워크에서 경로 쿼리를 더 빠르게 처리할 수 있습니다.
소셜 네트워크: 플랫폼은 수십억 명의 사용자 그래프에서 영향력 전파 및 최단 연결 경로를 더욱 효율적으로 계산할 수 있습니다.
공급망 최적화: 물류 회사는 향상된 계산 효율성을 통해 복잡한 유통 네트워크에서 배송 경로를 최적화할 수 있습니다.
란 두안, 샤오 마오, 런 한린, 탄 지한이 쓴 연구 논문 "지시된 단일 소스 최단 경로를 위한 정렬 장벽 깨기"는 청화대학교와 스탠포드대학교의 협업을 나타내며, 이론 컴퓨터 과학의 경계를 넓히는 데 있어 국제 학술 협력의 힘을 보여줍니다.
논문 : Breaking the Sorting Barrier for Directed Single-Source Shortest Paths