올해 4월에 발표된 이 논문은 O(m + n log n)를 깨는 최초의 결정론적 알고리즘으로, 시간 복잡도를 O(m log^(2/3) n)으로 줄였다네요. 참고로 sparse network일수록 효과가 좋대요. 41년만에 최단거리의 새로운 결과를 보여준 신-알고리즘.
일단 핵심은 기존 다익스트라가 매번 힙큐에서 넣고 뺄 때마다 log n 시간 복잡도를 가졌는데, 이 정렬을 줄이기 위해 벨만포드의 방식을 사용하여 분할정복하면 줄어든대요. 아직 완벽하게는 이해 못했는데 여튼 초록만 읽어도 섹시하네요.
https://arxiv.org/pdf/2504.17033