개념
다익스트라 알고리즘은 그래프에서 시작 노드로부터 다른 노드까지의 최단 경로를 찾는 알고리즘이다. 간선 비용이 음수가 아닐 때 사용된다.
탐색과의 관계
지도에서 집, 학교, 은행, 슈퍼 같은 장소를 노드로 두고 도로 거리를 비용으로 두면, 다익스트라 알고리즘으로 가장 짧은 경로를 찾을 수 있다.
간선 를 확인할 때 더 짧은 경로가 발견되면 거리를 다음처럼 갱신한다.
A star와의 차이
A star 알고리즘은 목표까지의 추정치 h(n)를 사용해 더 목표 지향적으로 탐색한다. 반면 다익스트라는 남은 거리 추정치를 사용하지 않고 현재까지의 비용 g(n)을 중심으로 확장한다.