네비게이션이 경로를 찾는 방법

Hook: Google Maps의 비밀

"Google Maps는 1초 만에 서울에서 부산까지 최적 경로를 찾는다. 이것이 가능한 이유는?"

순진한 접근: 모든 경로 탐색

Dijkstra의 천재적 발상 (1956)

"모든 경로를 볼 필요 없다. 현재까지 가장 가까운 곳부터 확장하면 처음 도착하는 것이 최단 경로다."

경로 탐색의 활용

분야	활용	알고리즘
네비게이션	최단/최적 경로	Dijkstra, A*
네트워크	패킷 라우팅	OSPF (Dijkstra 기반)
게임	NPC 이동	A*
물류	배송 최적화	Dijkstra + 휴리스틱
소셜	연결 고리	BFS

경로 탐색 문제 유형

1. Single Source (한 출발점 → 모든 도착점)

2. Single Pair (한 출발점 → 한 도착점)

3. All Pairs (모든 출발점 → 모든 도착점)

오늘 배울 알고리즘

알고리즘	특징	복잡도
Dijkstra	가중치 최단 경로	O((V+E) log V)
A*	휴리스틱 기반	더 빠름 (휴리스틱 품질에 따라)
Delta-Stepping	병렬 Dijkstra	대규모 그래프
All Shortest Paths	모든 최단 경로	다중 경로 탐색

Cypher의 기본 경로 탐색

한계: 가중치 무시, 대규모 그래프에서 느림 → GDS 알고리즘 필요!