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