Dijkstra(다익스트라)

Dijkstra(다익스트라)는 최단거리 탐색 알고리즘이라고도 부른다.

한 정점으로부터 다른 정점까지의 최단 경로를 구할 때 사용할 수 있다.

DFS(깊이 우선 탐색)와 BFS(넓이 우선 탐색)의 기본 개념이 연결되어 있는 모든 노드를 탐색한다 라면

다익스트라는 연결되어 있는 노드들간에 간선의 가중치가 존재하고 그 가중치를 기준으로 두 노드간의 최단 거리를 구한다는 개념이다.

현실에서 다익스트라 알고리즘은 GPS, 네비게이션 등에서도 이용된다.

하나의 최단거리를 구할 때 그 전의 최단거리 정보들을 사용하기 때문에 기본적으로 다이나믹 프로그래밍 문제에서 많이 다루는 알고리즘 중 하나이다.