알고리듬 Extra #1 최단경로 구하기 : 다익스트라를 일부만 정렬해서 최단거리 구하기

오늘 코딩애플님의 유튜브 영상을 보다가 특이한 댓글을 하나 발견해서 논문 찾아봤다.

보던 영상은 아래 링크로 올린다.  

개발자 1명이 실수하면 인터넷이 멸망한다고?

영상 내용과는 관계 없는 댓글이긴 한데...

댓글의 내용은 최단경로 구하기 문제를 다익스트라 알고리즘보다 더 빠르게 구하는 결정론적 방법에 대한 내용이었다.

보니까 갓 나온 따끈따끈한 논문이더라고?

Tsinghua University, Stanford University, Max Planck Institute for Informatics
이 세곳에서 공동 연구한 논문이었다.

[2504.17033] Breaking the Sorting Barrier for Directed Single-Source Shortest Paths

Breaking the Sorting Barrier for Directed Single-Source Shortest Paths

 

다익스트라 알고리듬(Dijkstra)

추후 다익스트라 알고리즘 자체에 대해 별도로 글을 쓰겠지만, 여기서는 간단히만 정리한다.

다익스트라의 핵심 아이디어는 다음과 같다.

• 큰 문제의 최적 해(최단경로)를 구할 때,
• 작은 부분 문제에서 최선을 하나씩 확정하고, 이를 합쳐 나가면 전체에서도 최선이 된다.

즉, “현재까지 가장 가까운 정점”을 하나씩 선택하면서 전체 경로를 완성하는 방식이다.

그래서 네비게이션이나 게임( NPC와 같은 게임 AI들의 이동 경로 문제, 미니맵 클릭을 통한 플레이어 캐릭터의 자동 경로 탐색 등 )과 같이 경로를 찾아야 하는 프로그램들은 최단 경로를 찾아낼 때 다익스트라 알고리듬 내지는 A-Star 알고리즘을 사용한다.

이 작은 부분에서의 최선을 찾기 위해서 우선순위 큐를 사용한다. 

항상 현재까지 가장 가까운 정점을 힙에서 꺼내고 그 정점에서 나가는 간선을 완화 하며 거리를 갱신해 나간다.

때문에 다익스트라 알고리듬은 정점과 간선의 갯수 (N + M)에 우선순위 큐를 유지하기 위한 비용(logN)을 합쳐서 최종적으로 O((N+M)logN)의 시간복잡도를 갖게 된다.

이 논문에서 주목한 것은 바로 logN의 비용을 줄이는 것이었다.

연구진은 방향 그래프에서 비음수 가중치를 가진 SSSP를 대상으로, 비교·덧셈 모델에서 결정론적 O(m · log^{2/3} n) 알고리듬을 제시했다.
다익스트라의 고전적 상한선 O(m + n log n)을 넘어서 정렬/우선순위 유지 단계의 로그 비용을 더 낮춘 것이 핵심이다.

이 논문에서는 다익스트라와 벨만-포드 두 가지 방식을 혼합하여 분할 정복 내지는 선택적 축소 기법 (Pivot/frontier shrink) 을 사용하여 검색 위치를 줄일 수 있다는 것이다.

굳이 매 단계 전체 후보에서 최소를 찾지 않고, 검색 범위를 계층/세그먼트(청크)로 쪼개 필요한 구간만 집중적으로 완화(relaxation)·확정하는 방식으로 후보 집합을 빠르게 줄인다.

이렇게 하면 “항상 전 범위를 우선순위로 정렬해 두어야 하는” 부담이 줄어들어, 결과적으로 정렬에 해당하는 비용을 log^{2/3} n 수준까지 낮춘다.

복잡도 관점에서 O(m · log^{2/3} n)은 간선 수에 거의 선형적으로 비례하므로, m ≪ n^2인 희소 그래프에서 체감 이득이 특히 두드러진다.

다음과 같은 그래프가 있다고 생각해보자

A에서 출발하여 F로 가는 경로는

다음과 같이 시뮬레이션 된다.

다익스트라 (A → F)

초기 상태

 

dist: A=0, B=∞, C=∞, D=∞, E=∞, F=∞ PQ: [(0, A)]

---

1단계: A 확정

• Pop: (0, A)
• Relax:
  • A→B (3) → dist[B]=3
  • A→D (15) → dist[D]=15
  • A→F (30) → dist[F]=30

 

PQ: [(3, B), (15, D), (30, F)]

---

2단계: B 확정

• Pop: (3, B)
• Relax:
  • B→D (5) → dist[D]=8 (갱신)
  • B→F (10) → dist[F]=13 (갱신)

 

PQ: [(8, D), (13, F), (15, D), (30, F)]

---

3단계: D 확정

• Pop: (8, D)
• Relax:
  • D→C (3) → dist[C]=11
  • D→E (4) → dist[E]=12
  • D→F (1) → dist[F]=9 (갱신)

 

PQ: [(9, F), (11, C), (12, E), (13, F), (15, D), (30, F)]

---

4단계: F 확정

• Pop: (9, F) → 도착점 확정, 종료

 

PQ: [(11, C), (12, E), (13, F), (15, D), (30, F)]

---

결과

• 최단 거리: 9
• 최단 경로: A → B → D → F

지금 그래프에서는 경로 수가 적지만, 만약 하나의 노드에 연결된 경로가 매우 많아진다면 이 알고리듬의 효과가 두드러진다.

예를 들어 정점이 100개 있고, A에서 출발하는 간선이 80개 있다고 해보자. 첫 번째 단계에서 A를 확정하면, 이 80개의 간선이 모두 우선순위 큐에 삽입된다.

만약 이 중에서 바로 최단 경로가 확정된다면, 그 순간 80개 원소는 다음 단계에서 정리되고 대신 B에서 뻗어나가는 간선 수(예: 50개)가 새로 삽입된다.

하지만 만약 바로 확정되지 않는다면, 큐 안의 80개 원소가 그대로 남아 있게 되고, 매 단계마다 우선순위 큐 연산을 거쳐야 한다. 결국 이 연산의 log N 비용이 전체 시간복잡도를 지배하게 된다.

이 논문에서는 한 스텝에서 확인해야 하는 범위를 80개 전부가 아니라, 더 작은 단위(예: 8개)씩으로 쪼개서 관리하자는 것이다.

즉, 80개를 한꺼번에 우선순위 큐에서 정렬·유지하지 않고, 8개짜리 묶음 10개로 나눠 관리한다. 이렇게 하면 비교 연산 횟수는 조금 늘어나지만(각 정점에 대해 10번의 삽입) 한 번에 처리하는 큐 크기가 작아져, 우선순위를 유지하는 데 필요한 비용이 크게 줄어든다.

단순 비교로 설명하자면, 80개의 간선을 한꺼번에 관리하면 배열 방식으로는 80 * 80 = 6400번 비교가 필요하다.
하지만 이를 8개씩 나누어 관리하면 10 * 10 * 8 = 800번 수준으로 줄어든다.

물론 이는 Naive한 방법으로 설명한 비유일 뿐 실제 우선순위 큐는 힙 구조를 사용하기 때문에 훨씬 더 효율적이다.
그럼에도 불구하고 핵심은, 전부 다 정렬하지 않고 작은 단위로 관리하면 로그 비용이 확 줄어든다는 점이다.

이 논문 내용이 실제로 적용될지는 미지수다. 오랜 기간 다익스트라가 사용되온 이유가 있고, 이 논문 또한 오랜 기간 검증되어야 할 테니까 말이다. 

그럼에도 불구하고, 기존의 상한선을 깨뜨렸다는 사실만으로도 의미가 크다.
무엇보다도 새로운 지식을 기존 지식(다익스트라·벨만-포드 등)과 연결해 직관적으로 이해할 수 있다는 점, 그리고 이 아이디어가 다른 문제에 응용될 수 있다는 가능성을 생각하면, 단순히 “신기하네, 나중에 써먹어야지”를 넘어서 토론할 만한 주제거리가 된다는 점에서 가치가 있다.

이상 아직 주니어조차 되지 못한

한참 배울게 남아있는 개발자 지망 취준생으로서의

짧은 논문 리뷰였다.