중국 연구진이 41 년 만에 최단 경로 알고리즘의 새로운 기록을 세움!

요약

중국 청화대학교 연구진이 다익스트라 알고리즘(Dijkstra's Algorithm)의 오랜 효율성 기록을 깬 새로운 최단 경로 알고리즘을 개발했습니다. 이들은 기존 방식처럼 노드를 완전히 정렬하는 과정을 생략하고, 벨만-포드 알고리즘과 '재귀적 부분 정렬' 기법을 결합하여 문제를 해결했습니다. 그 결과, 단일 원천 최단 경로(SSSP) 문제의 시간 복잡도를 $O(m ext{ } ext{log}^{2/3} n)$으로 개선하며 이론 컴퓨터 과학 분야에 큰 변화를 가져왔습니다.

핵심 포인트

• 41년 만에 최단 경로 알고리즘의 효율성 기록이 갱신되었습니다.
• 기존 다익스트라 알고리즘은 '거리 정렬'이라는 수학적 한계 때문에 성능 개선에 제약이 있었습니다.
• 새로운 접근 방식은 노드를 완전히 정렬하지 않고, 벨만-포드와 재귀적 부분 정렬을 결합하여 경로를 찾습니다.
• 개선된 시간 복잡도는 $O(m ext{ } ext{log}^{2/3} n)$으로, 기존의 $O(m + n ext{ } ext{log} n)$보다 우수합니다.
• 이 발견은 웹이나 글로벌 물류와 같은 거대한 희소 그래프에서 최적 경로 탐색 속도를 획기적으로 높일 수 있음을 의미합니다.