65년 정설 깬 새 알고리즘, 다익스트라보다 빠르다...실무 적용은 시기상조

칭화대 연구팀, 정렬 장벽 돌파한 최단경로 알고리즘 개발해 STOC 최우수상 수상

[한국정보기술신문] 1959년 개발된 이래 컴퓨터 과학의 필수 알고리즘으로 자리매김한 다익스트라 알고리즘보다 이론적으로 빠른 새로운 최단경로 탐색 알고리즘이 등장했다. 하지만 실제 프로덕션 환경에서의 적용 가능성에 대해서는 회의적인 시각이 공존하고 있다.

칭화대학교 학제간정보과학연구소의 단란 부교수 연구팀은 지난 2025년 ACM 컴퓨팅 이론 심포지엄에서 방향 그래프의 단일 출발점 최단경로 문제를 O(m log^(2/3) n) 시간 복잡도로 해결하는 알고리즘을 발표해 최우수 논문상을 수상했다. 연구팀에는 단란, 마오자이, 마오샤오, 슈신카이, 인롱후이가 참여했으며, 이 중 마오샤오는 ICPC 세계 챔피언 출신으로 알려졌다.

정렬 장벽 극복이 핵심

새 알고리즘의 핵심은 다익스트라 알고리즘이 필수적으로 요구하던 정렬 과정을 우회한다는 점이다. 다익스트라 알고리즘은 우선순위 큐를 사용해 매번 가장 가까운 노드를 선택하는 과정에서 정렬 작업이 불가피했고, 이는 O(m + n log n)이라는 시간 복잡도의 한계로 작용했다.

연구팀은 벨만-포드 알고리즘의 일부 기법을 결합하고, 전체 노드를 정렬하는 대신 네트워크의 각 영역에서 대표 노드 그룹만 추적하는 방식을 고안했다. 프론티어 노드들을 클러스터링하고 소수의 대표 노드만으로 작업함으로써 정렬에 드는 시간을 대폭 줄였다. 특히 희소 그래프에서 m이 대략 O(n) 수준일 때 점근적으로 더 빠른 성능을 보인다.

이론적 돌파구, 실무 적용은 별개

하지만 컴퓨터 네트워크 분야의 전문가들은 실제 프로덕션 환경 적용에 신중한 입장이다. 컴퓨터 네트워크 교과서 시스템스 어프로치의 저자인 래리 피터슨은 자신의 블로그를 통해 이론적 개선이 실무에서 의미 있는 차이를 만들기 어렵다고 지적했다.

피터슨은 실제 라우팅 수렴 과정에서 최단경로 계산은 전체 시간의 일부에 불과하다고 설명한다. 링크 상태 패킷 전송 및 전파 지연, 패킷 수신 및 프로세스 디스패치, 라우팅 정보 베이스 업데이트, 포워딩 테이블 계산 및 라인 카드 업데이트 등 다른 요소들의 최적화가 이미 상당히 진행되어 2003년부터 1초 이하의 라우팅 수렴이 일상화됐다는 것이다.

구현 복잡도와 규모 문제

새 알고리즘은 다익스트라에 비해 구현이 복잡하다는 단점도 있다. OSPF 같은 링크 상태 라우팅 프로토콜의 명세는 구현자들에게 다익스트라 알고리즘 사용을 권장하며, 수십 년간 수많은 최적화가 이뤄져 왔다. 피터슨은 수 밀리초를 절약하기 위해 엔지니어들에게 복잡한 하이브리드 벨만-포드와 다익스트라 접근법을 이해시키는 것보다 OSPF 명세를 참조하는 편이 낫다고 강조했다.

또한 이론적 복잡도 개선이 의미를 가지려면 충분히 큰 네트워크 규모가 필요하다. 작은 규모에서는 상수 인자 차이로 인해 덜 확장 가능한 접근법이 오히려 나은 성능을 보일 수 있다는 점도 고려해야 한다.

향후 전망과 응용 가능성

그럼에도 이번 연구가 학계에 던진 의미는 크다. 40년 이상 깨지지 않을 것으로 여겨진 정렬 장벽이 돌파 가능함을 증명했고, 다른 그래프 알고리즘 개선에도 영감을 줄 수 있다. 대규모 지도 애플리케이션이나 소셜 그래프 분석, 추천 시스템 같은 특정 분야에서는 실제 적용 가능성도 있다.

연구팀의 알고리즘은 결정론적이며, 비교-덧셈 모델 하에서 작동하고, 음이 아닌 실수 가중치를 가진 방향 그래프에 적용된다. 동일 길이 경로 문제를 해결하기 위해 경로 길이, 홉 수, 정점 레이블을 사용한 전순서를 강제하며, 고차수 노드를 더미 정점으로 대체해 상수 차수 그래프로 변환하는 등의 기법을 활용한다.

피터슨은 언젠가 누군가 이 새로운 최단경로 접근법을 다익스트라 논문이나 OSPF 명세만큼 명확하게 설명하는 날이 올 수 있다고 전망하면서도, 프로덕션 라우터에서 다익스트라 알고리즘이 대체되는 일은 당분간 없을 것이라고 결론지었다. 알고리즘 연구의 새로운 장을 연 이번 성과가 실무 환경에서 꽃을 피우기까지는 더 많은 시간과 검증이 필요해 보인다.

한국정보기술신문 정보통신분과 김민재 기자 news@kitpa.org