# 41년만에 새로운 최단경로 알고리즘을 발견

> Clean Markdown view of GeekNews topic #23112. Use the original source for factual precision when an external source URL is present.

## Metadata

- GeekNews HTML: [https://news.hada.io/topic?id=23112](https://news.hada.io/topic?id=23112)
- GeekNews Markdown: [https://news.hada.io/topic/23112.md](https://news.hada.io/topic/23112.md)
- Type: news
- Author: [pjy6076](https://news.hada.io/@pjy6076)
- Published: 2025-09-16T13:44:19+09:00
- Updated: 2025-09-16T13:44:19+09:00
- Original source: [arxiv.org](https://arxiv.org/pdf/2504.17033)
- Points: 73
- Comments: 18

## Summary

칭화대와 스탠포드 연구진이 **최단경로(SSSP) 문제**에서 기존 **디익스트라 알고리즘**의 한계를 40여 년 만에 뛰어넘는 개선을 달성했습니다. 새로운 방법은 시간복잡도를 **O(m·log^(2/3) n)** 으로 낮췄습니다.

## Topic Body

중국 칭화대(Tsinghua University) 연구진이 스탠포드 대학과 협력해, 전통적 최단 경로(single-source shortest path, SSSP) 문제에 대한 계산 복잡도 측면에서 큰 발전을 이루었음. 이 연구는 2025년 STOC 학회에서 Best Paper 상을 수상.  
   
전통적으로 많이 쓰이는 방법이 디익스트라(Dijkstra)의 알고리즘으로, 시간 복잡도가 O(m + n log n) (n = 노드 수, m = 간선 수) 형태임.  
log n항은 우선순위 큐(priority queue)나 정렬(sorting)과 관련된 부분으로, 지난 40년간 이 부분을 뛰어넘는 개선이 없었음.   
  
새로운 알고리즘은 시간 복잡도를 O(m · log^(2/3) n) 으로 줄였음.   
log^(2/3) n 은 log n 보다 느리게 증가하므로 (즉 log n 보다 작게 늘어남), 노드 수가 매우 클 경우 차이가 커짐.

## Comments



### Comment 44157

- Author: slowmo
- Created: 2025-09-22T14:37:55+09:00
- Points: 1

2000년대 말에 차량 네비게이션 소프트웨어 업체에서 일하면서 경로 탐색 모듈을 개발하던 추억(?)이 떠오르네요.   
Dijkstra는 네비게이션 경로 탐색엔 너무 느려서 안 쓰고 휴리스틱 개선 버전인  A*(A Star) 검색을 사용하죠. 찾아보니 A*는 SSSP가 아니라 SPSP(Single-Pair Shortest Path) 알고리즘이군요.

### Comment 44014

- Author: qpalzmxn
- Created: 2025-09-18T10:43:25+09:00
- Points: 1

sparse한 경우에 빠른 알고리즘이랑 뛰어넘었다고 하기엔 애매한듯 합니다

### Comment 43988

- Author: helio
- Created: 2025-09-17T20:37:31+09:00
- Points: 1

CLRS 개정된 지 그리 오래 되지 않았을텐데 새로 찍나요

### Comment 43978

- Author: kmc0722
- Created: 2025-09-17T15:18:44+09:00
- Points: 1

과거에 등장해 현재까지도 인기많은 밴드인 비틀즈나 오아시스의 41년만의 새로운앨범이 나온느낌이네요. 일단 놀람과 흥미를 돋구는 ㅎㅎ

### Comment 43947

- Author: brainypooh
- Created: 2025-09-17T08:40:50+09:00
- Points: 1

미국이 이미 있었을지도? ㄷㄷㄷ

### Comment 43943

- Author: devstudyman7
- Created: 2025-09-17T02:44:52+09:00
- Points: 1

아름답네 ㅎㄷㄷ

### Comment 43940

- Author: ahwjdekf
- Created: 2025-09-17T00:38:17+09:00
- Points: 1

중국이 요즘 치고 나가네

### Comment 43939

- Author: onetoday
- Created: 2025-09-16T23:55:21+09:00
- Points: 1

알고리즘 이름이 어떻게 정해지려나

### Comment 43936

- Author: belline0124
- Created: 2025-09-16T22:21:21+09:00
- Points: 1

곧 누군가 저 제한 조건으로 백준에 문제 내겠네요 두근두근

### Comment 43934

- Author: fastkoder
- Created: 2025-09-16T22:02:15+09:00
- Points: 1

추억의 다익스트라..

### Comment 43926

- Author: chebread
- Created: 2025-09-16T18:18:00+09:00
- Points: 1

와... 대박이네요...

### Comment 43920

- Author: channprj
- Created: 2025-09-16T18:06:52+09:00
- Points: 1

멋지네요.

### Comment 43919

- Author: woogi
- Created: 2025-09-16T18:04:39+09:00
- Points: 1

와우......

### Comment 43918

- Author: pmc7777
- Created: 2025-09-16T17:56:42+09:00
- Points: 1

이게 되네요...

### Comment 43917

- Author: kimjoin2
- Created: 2025-09-16T17:56:11+09:00
- Points: 1

캬아~~

### Comment 43915

- Author: roxie
- Created: 2025-09-16T16:40:46+09:00
- Points: 1

키야....

### Comment 43910

- Author: beoks
- Created: 2025-09-16T15:54:32+09:00
- Points: 1

알고리즘 수업 내용이 추가되겠군요 ㅋㅋㅋ

### Comment 43935

- Author: jhk0530
- Created: 2025-09-16T22:13:06+09:00
- Points: 1
- Parent comment: 43910
- Depth: 1

아이고...