Dijkstra1 Shortest Paths(다익스트라 알고리즘 (Dijkstra Algorithm)) 이번에는 다익스트라 알고리즘에 대해서 공부를 해보았다. 다익스트라 알고리즘은 단일 시작점으로부터 다른 노드들까지의 최단 경로를 구하는 알고리즘이다. 또한, 음의 가중치를 허용하지 않는 최단경로를 말한다. 위의 그림을 설명하자면, 시작점을 제외한 모든 저점과 시작점 사이의 거리를 무한으로 표현하고 다음과 같은 수행을 반복한다. 1. 현재 선택한 정점(처음엔 시작점)에 곧장 연결되고, 아직 방문하지 않은 정점들을 모두 본다. 2. 선택한 정점과 보고있는 정점 사이의 거리와 시작 정점과 선택한 정점까지의 최단거리의 합이 현재까지 구한 시작 정점과 보고 있는 정점 사이의 거리보다 짧을 경우, 이를 갱신해준다. 3. 1, 2번 수행이 모두 끝난 이후, 아직 방문하지 않은 정점들 중 시작점과의 거리가 가장 짧은 정.. 2021. 11. 2. 이전 1 다음
