경로 탐색 알고리즘

너비 우선 탐색(BFS)

그래프를 층별로 탐색한다. 

한번 거친 노드 순서를 저장한 후 다시 꺼내는 선입선출 원칙으로 탐색한다.(큐 데이터구조)

 

깊이우선탐색(DFS)

경로 하나의 모든 층을 탐색한 후 그 다음에 다른 경로의 모든 층을 탐색한다.

재귀호출이나 스택을 사용한다.

 

출처:나무위키

다익스트라(Dijkstra) 알고리즘

가중 그래프에서 동작하고 그래프의 시작 노드에서 목표노드까지의 최단 경로(최소 비용)를 찾는다.

그래프의 가중치를 비용이라고 하며, 비용이 음수가 아니어야한다. 

무정보탐색으로 많은 시간과 자원을 소비한다는 한계점이있다.

(참고) 벨먼-포드 알고리즘은 가중치가 음수인 그래프에서도 동작한다.

A*알고리즘

휴리스틱 알고리즘(확률론을 토대로 문제의 대략적인 해결책을 제공)의 범주에 속한다. 

데이크스트라 알고리즘 + 최선우선탐색(휴리스틱)이 결합하여 전체 순회비용이 가장 낮은 경로를 선택한다.