컴퓨터 과학 혁신, 다익스트라 알고리즘 60년 지배 깨뜨리다

[한국정보기술신문] 컴퓨터 과학의 기초 알고리즘 분야에서 획기적인 발전이 이뤄졌다. 60여 년간 그래프 최단경로 문제의 표준으로 여겨져 온 다익스트라 알고리즘의 시간복잡도 한계를 뛰어넘는 새로운 알고리즘이 개발됐다. 칭화대학교, 스탠포드대학교, 독일 막스플랑크 정보학연구소 공동연구팀이 개발한 이 알고리즘은 기존 O(m+n log n) 시간복잡도를 O(m log^(2/3) n)으로 개선해 희소 그래프에서 획기적인 성능 향상을 달성했다.

단일 소스 최단경로(SSSP) 문제는 주어진 출발점에서 그래프의 모든 정점까지의 최단거리를 찾는 문제로, 네비게이션 시스템, 네트워크 라우팅, 물류 최적화 등 현대 디지털 사회의 핵심 기술들에 광범위하게 활용되고 있다. 1959년 에드스허 다익스트라가 제안한 다익스트라 알고리즘은 이 문제를 해결하는 가장 효율적인 방법으로 인정받아왔다. 특히 피보나치 힙과 같은 고급 자료구조와 결합했을 때 O(m+n log n) 시간복잡도를 달성하며, 여기서 m은 간선 수, n은 정점 수를 의미한다.

그러나 이번 연구는 다익스트라 알고리즘이 최적이 아니라는 것을 증명했다. 연구팀의 새로운 알고리즘은 희소 그래프에서 기존 방법보다 현저히 빠른 성능을 보여준다. 논문의 제1저자인 칭화대학교 단란 교수는 "이번 연구는 비교-덧셈 모델에서 정렬 장벽을 깨뜨린 최초의 유향 그래프 알고리즘"이라고 설명했다.

새로운 알고리즘의 핵심은 두 가지 전통적인 접근법의 혁신적 결합에 있다. 다익스트라 알고리즘은 우선순위 큐를 통해 매번 출발점으로부터 최소 거리를 가진 정점을 추출하여 처리하지만, 이 과정에서 정점들을 거리순으로 정렬해야 하므로 최소 Θ(n log n)의 시간이 필요하다. 반면 벨만-포드 알고리즘은 동적 프로그래밍을 기반으로 모든 간선을 여러 번 완화하여 정렬 없이도 k개 이하의 간선을 포함하는 최단경로를 O(mk) 시간에 찾을 수 있다.

연구팀은 이 두 방법을 재귀적 분할 기법을 통해 결합했다. 알고리즘 실행 중 다익스트라의 우선순위 큐가 유지하는 "프론티어" 집합의 크기를 효과적으로 줄이는 것이 핵심 아이디어다. 기존에는 프론티어가 Θ(n)개의 정점을 포함할 수 있어 전체 순서를 유지해야 했지만, 새로운 방법은 프론티어 크기를 관심 정점 수의 1/log^Ω(1)(n)로 제한할 수 있다.

알고리즘의 또 다른 핵심 혁신은 "피벗 발견" 기법이다. 주어진 상한 B보다 작은 거리를 가진 모든 거리를 계산하고자 할 때, 연구팀은 프론티어 집합 S로부터 k = log^Ω(1)(n) 단계의 벨만-포드 완화를 수행한다. 이 과정을 통해 k개 미만의 정점을 거치는 최단경로를 가진 모든 정점은 완료되고, 나머지는 크기가 k 이상인 최단경로 트리의 "피벗"들에만 의존하게 된다.

이러한 피벗의 개수는 전체 관심 정점 수를 k로 나눈 값으로 제한되므로, 프론티어를 효과적으로 축소할 수 있다. 연구팀은 이를 통해 다익스트라의 동적 프론티어 관리 대신 분할 정복 절차를 사용하여 log n/t 단계로 구성된 알고리즘을 설계했다.

새로운 알고리즘의 시간복잡도 O(m log^(2/3) n)는 희소 그래프에서 특히 의미가 크다. 예를 들어, 100만 개 정점을 가진 그래프에서 기존 다익스트라 알고리즘의 log n 항이 약 20인 반면, 새 알고리즘의 log^(2/3) n 항은 약 7.4로 상당한 개선을 보여준다. 특히 m이 n에 비해 상대적으로 작은 희소 그래프에서는 더욱 극적인 성능 향상을 기대할 수 있다.

이론적 관점에서 이 연구는 여러 중요한 의미를 갖는다. 첫째, 다익스트라 알고리즘이 최적이 아님을 증명했다. 둘째, 무향 그래프뿐만 아니라 유향 그래프에서도 정렬 장벽을 깨뜨릴 수 있음을 보였다. 셋째, 기존의 무작위 알고리즘과 달리 완전히 결정적인 알고리즘을 제시했다.

연구팀이 채택한 비교-덧셈 모델은 실수 가중치를 가진 그래프에서 자연스러운 계산 모델로, 간선 가중치에 대해 비교와 덧셈 연산만을 허용하며 각 연산은 단위 시간을 소모한다고 가정한다. 이는 실제 응용에서 그래프의 가중치가 실수인 경우가 많다는 점을 고려할 때 매우 실용적인 모델이다.

기존에 무향 그래프에서는 페티와 라마찬드란이 제안한 계층 기반 알고리즘이 O(mα(m,n) + min{n log n, n log log r}) 시간복잡도를 달성했지만, 유향 그래프에서는 다익스트라의 O(m+n log n) 한계를 뛰어넘지 못했다. 이번 연구는 유향 그래프에서 이러한 정렬 장벽을 처음으로 깨뜨린 성과다.

새로운 알고리즘은 크게 세 가지 주요 구성요소로 이뤄진다. 먼저 BMSSP(Bounded Multi-Source Shortest Path) 서브루틴이 핵심이다. 이는 주어진 상한 B와 소스 집합 S에 대해 거리가 B보다 작고 S의 어떤 정점을 거치는 최단경로를 가진 모든 정점의 실제 거리를 계산한다.

FindPivots 알고리즘은 주어진 프론티어 S에서 실제로 중요한 피벗들만을 선별해낸다. k번의 완화 단계를 수행한 후, k개 이상의 정점을 포함하는 최단경로 트리의 루트들만을 피벗으로 선정하여 프론티어 크기를 효과적으로 줄인다.

마지막으로 부분 정렬 힙 자료구조는 전체를 정렬하지 않고도 필요한 만큼의 최솟값들을 효율적으로 추출할 수 있게 해준다. 이는 블록 기반 연결 리스트와 자기균형 이진 탐색 트리를 결합한 구조로, 삽입, 일괄 전치, 추출 연산을 효율적으로 지원한다.

알고리즘의 분석을 단순화하기 위해 연구팀은 임의의 그래프를 상수 차수 그래프로 변환하는 고전적 기법을 사용했다. 각 정점 v를 가중치가 0인 간선들로 강하게 연결된 정점들의 사이클로 대체하고, 원래 간선 (u,v)는 해당 사이클의 적절한 정점들 사이의 간선으로 변환한다. 이 변환은 최단경로를 보존하면서도 모든 정점의 입차수와 출차수를 최대 2로 제한한다.

이러한 변환을 통해 알고리즘의 분석이 크게 단순해지며, 실제 구현에서도 복잡한 차수 처리 문제를 우회할 수 있다. 변환된 그래프는 O(m)개의 정점과 간선을 가지므로 전체 시간복잡도에는 영향을 주지 않는다.

알고리즘의 정확성을 보장하기 위해 연구팀은 모든 경로가 서로 다른 길이를 갖는다는 가정을 도입했다. 이는 두 가지 목적을 위한 것으로, 첫째는 모든 정점의 predecessor가 트리 구조를 유지하도록 하고, 둘째는 같은 거리 추정값을 가진 정점들 사이의 상대적 순서를 제공하기 위함이다.

실제로는 경로들을 <길이, 정점 수, 역순 정점 시퀀스> 형태의 튜플로 표현하고 사전식 순서로 정렬함으로써 전순서를 구성한다. 중요한 것은 이러한 비교가 predecessor 정보만을 이용해 O(1) 시간에 수행될 수 있다는 점이다.

알고리즘의 정확성은 수학적 귀납법을 통해 엄밀하게 증명된다. 핵심 아이디어는 각 재귀 단계에서 두 가지 명제를 유지하는 것이다: (a) 거리가 상한보다 작은 모든 미완료 정점이 현재 프론티어를 거치는 경로를 갖는다는 것과, (b) 특정 거리 구간의 정점들이 데이터구조 D의 정점들과 일대일 대응된다는 것이다.

이러한 불변량들은 알고리즘의 각 단계에서 보존되며, 최종적으로 반환되는 집합 U가 정확히 요구되는 정점들을 포함하고 모두 완료 상태임을 보장한다. 특히 Ui들이 서로소이고 거리 순으로 정렬된다는 중요한 성질도 증명된다.

시간복잡도 분석에서 핵심은 매개변수 k = ⌊log^(1/3)(n)⌋와 t = ⌊log^(2/3)(n)⌋의 선택이다. 이 값들은 다양한 연산들의 비용을 균형맞추도록 최적화되었다. FindPivots 연산은 O(|U|k) 시간이 걸리고, 데이터구조 연산들은 O(log k + t) 시간이 걸리며, 전체 재귀 깊이는 (log n)/t로 제한된다.

모든 구성요소의 비용을 합산하면 전체 시간복잡도는 O(m log^(2/3) n)이 된다. 이는 기존 O(m + n log n)보다 희소 그래프에서 점근적으로 더 우수한 성능을 제공한다.

그래프 알고리즘 분야에서 정렬 장벽을 깨뜨리려는 시도는 오랫동안 계속되어 왔다. 야오는 1975년 최소 신장 트리 문제에서 O(m log log n) 알고리즘을 제안했고, 이는 후에 무작위 선형 시간 알고리즘으로 개선되었다. 가보우와 타잔은 s-t 병목 경로 문제를 O(m log* n) 시간에 해결했으며, 이는 후에 무작위 O(mβ(m,n)) 시간으로 개선되었다.

단일 소스 병목 경로 문제에서는 두안 등이 무작위 O(m√(log n)) 시간 알고리즘을 제안했다. 그러나 단일 소스 최단경로 문제에서는 이번 연구 이전까지 유향 그래프에서 정렬 장벽을 깨뜨린 연구가 없었다. 이번 연구는 또한 무향 그래프에서도 최초의 결정적 알고리즘이라는 의미를 갖는다.

이번 연구의 성과는 다양한 실용적 응용 분야에 직접적인 영향을 미칠 것으로 예상된다. 교통 네트워크에서의 최적 경로 탐색, 통신 네트워크에서의 라우팅 프로토콜, 소셜 네트워크 분석, 공급망 최적화 등에서 더 빠른 성능을 제공할 수 있다. 특히 대규모 희소 그래프를 다루는 현대의 빅데이터 응용에서는 상당한 성능 향상을 기대할 수 있다.

클라우드 컴퓨팅과 분산 시스템에서도 이 알고리즘의 효율성은 중요한 의미를 갖는다. 네트워크 지연시간 최소화, 데이터 센터 간 최적 라우팅, 콘텐츠 전송 네트워크 최적화 등에서 실질적인 개선을 가져올 수 있을 것이다.

이번 연구는 컴퓨터 과학의 가장 기초적이면서도 중요한 문제 중 하나에서 60년간 지속된 한계를 돌파한 역사적 성과다. 다익스트라 알고리즘이 최적이 아니라는 것을 증명하고, 실제로 더 빠른 알고리즘을 제시함으로써 이론적 한계와 실용적 가능성을 동시에 확장했다. 이는 단순히 하나의 알고리즘 개선을 넘어서, 그래프 알고리즘 전반에 대한 새로운 관점과 기법을 제공한다는 점에서 그 의의가 크다.

연구팀의 혁신적 접근법은 전통적인 두 방법론의 창의적 결합을 통해 기존 한계를 뛰어넘는 전형적인 사례를 보여준다. 이는 향후 다른 계산 문제들에서도 유사한 돌파구가 가능함을 시사하며, 알고리즘 이론 발전의 새로운 장을 여는 출발점이 될 것으로 기대된다.

해당 연구에 대한 논문은 아래 링크에서 확인해볼 수 있다.