| 알고리즘 | 설명 | 장점 | 단점 | 사용 사례 |
| BFS | 시작 노드에서 가까운 노드부터 차례로 탐색 | 간선 가중치가 동일할 때 최단 경로 보장, 구현 단순 | 메모리 사용량 큼(큐 필요), 가중치 있는 그래프 부적합 | 미로 최단 경로, 네트워크 탐색 |
| DFS | 한 경로를 끝까지 탐색한 후 돌아와 다른 경로 탐색 | 구현 간단, 메모리 사용 적음, 모든 경로 탐색 가능 | 최단 경로 보장 안 됨, 사이클 처리 필요 | 경로 존재 여부 확인, 퍼즐 탐색 |
| Dijkstra | 단일 시작 노드 → 그래프 내 모든 노드 최단 경로 계산 | 음수 가중치만 없으면 최단 경로 정확히 계산, 다양한 네트워크 최적화 활용 | 시간 복잡도 높음(O(E log V)), 음수 가중치 불가 | GPS 내비게이션, 통신망 최적화 |
| A* | 단일 시작 노드 → 특정 목표 노드까지 최단 경로 탐색 (휴리스틱 사용) | 실제 최단 경로를 빠르게 탐색, 효율적 경로 탐색 가능 | 휴리스틱 설계 중요, 잘못된 휴리스틱 → 성능 저하 | 게임 AI 길찾기, 로봇 경로 탐색 |