알고리즘/다익스트라(Dijkstra) (1) 썸네일형 리스트형 [Algorithm] 다익스트라(Dijkstra) 1. 개요 - 단일 출발지 최단거리 알고리즘 - 가중 그래프에서 사용할 수 있다. - 구현에 우선 순위 큐가 사용되며, BFS와 거의 유사하다. 2. 설명 다익스트라 알고리즘의 핵심 개념은, 각 정점 간 최단 거리를 구하면, 결국 출발지를 기준으로 모든 정점에 대한 최단 거리를 구할 수 있다는 것이다. 이는 BFS과 같이 너비 탐색을 하며, 탐색 시간을 줄이기 위해 "우선 순위 큐"를 사용하게 된다. - 초기 각 정점의 최단 거리는 모두 무한 값으로 설정이 되어야 한다. - 우선 순위 큐에 들어가는 정보는 (시작점 - 현재 정점 까지의 거리, 현재 정점)과 같다. - 시작 정점은 우선 순위 큐에 넣을 때 거리 0으로 지정하여 넣는다. - 시작 정점의 최단 거리는 0 이다. 1) 동작 절차 다익스트라 알고.. 이전 1 다음
