경로 탐색 알고리즘 비교

Dijkstra 알고리즘

핵심 원리

시각적 예시

조건

⚠️ 양수 가중치만 지원

음수 가중치가 있으면 Bellman-Ford 사용 (GDS 미지원)

A* 알고리즘

Dijkstra의 한계

A*의 해결책: 휴리스틱

GDS에서 A*

Delta-Stepping

대규모 그래프 문제

Delta-Stepping 아이디어

GDS에서 Delta-Stepping

알고리즘 선택 가이드

시간 복잡도 비교

알고리즘	시간 복잡도	적합한 경우
Dijkstra (힙)	O((V+E) log V)	중소규모
A*	O(b^d) (휴리스틱 의존)	한 쌍, 좌표 있을 때
Delta-Stepping	O(V + E) (병렬화)	대규모 그래프
Floyd-Warshall	O(V³)	작은 그래프 All Pairs

Cypher vs GDS

기능	Cypher	GDS
가중치	X	O
대규모	느림	빠름
병렬	X	O
알고리즘	shortestPath만	다양