공부하는 블로그

Dijkstra Algorithm ? 다익스트라 알고리즘(Dijkstra Algorithm)은 가중치를 가진 그래프에서 최단 경로를 탐색하는 알고리즘이다. 단, 가중치가 양수일 경우에만 사용이 가능하다. 다익스트라 알고리즘의 기본 로직은 출발 정점을 기준으로 연결되어 있는 정점들을 추가해가며 최단 거리를 갱신해나간다. 이러한 방식으로 출발 정점에서부터 다른 모든 정점까지의 최단 경로를 구할 수 있다. 그 과정은 다음과 같다. 1. 출발 정점으로부터 각 정점에 도달하는데까지 걸리는 시간을 계산한다. (연결이 되지 않았다면 가중치는 ∞) 2. 방문하지 않은 정점 중에서 제일 짧은 시간이 걸리는 정점을 찾는다. 3. 찾아낸 정점에서 이웃 정점에 도달하는데 걸리는 시간을 계산한다. 만약 이전에 기록한 시간보다 ..