개요
Edsger Dijkstra가 1956년 제안하고 1959년 발표한 단일 출발점 최단경로(SSSP) 알고리즘. 그래프에서 한 노드로부터 모든 다른 노드까지의 최단 거리를 우선순위 큐로 거리순 정렬하며 찾아낸다.
핵심 정보
- 발표 연도: 1959 (구상은 1956)
- 시간 복잡도: O(m + n log n) (피보나치 힙 기준)
- 핵심 원리: 노드를 거리순으로 정렬해 순차 확장 (sorting barrier)
- 응용: Google Maps 라우팅, 인터넷 패킷 라우팅, 항공편 검색
- 이론적 위치: 2024년 Robert Tarjan이 “정렬 기반 SSSP의 최적 효율성” 증명
- 2026 돌파: 칭화대팀이 O(m log^(2/3) n)로 최적성 정설 부정
주요 발언 / 기여
1984년 이래 40년간 SSSP 문제의 표준이자 이론적 한계 기준점. “sorting barrier”라는 패러다임을 만든 알고리즘.
관계
- 20260513-tsinghua-sssp-breakthrough — 후속: 41년 만의 결정론적 개선