[Algorithm] Dijkstra 알고리즘에 대해 알아보자
다익스트라(dijkstra) 알고리즘은 '최단 경로'를 찾을 때 유용하게 쓰인다. 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이라고 할 수 있다. 알고리즘의 아이디어 1. 출발 노드와 도착 노드를 설정한다. 2. 알고 있는 모든 거리값을 부여한다. 3. 출발 노드부터 시작하여 방문하지 않은 인접 노드를 방문하여 둘 사이의 거리를 계산한다. 이때 이미 알고 있는 거리보다 짧으면 해당 거리를 갱신한다. 4. 현재 노드에 인접한 모든 노드를 방문했다면 해당 노드는 모든 방문을 끝낸 것이므로 미방문 노드에서 없앤다. 5. 모든 미방문 노드를 방문했다면 알고리즘을 종료한다. 해당 알고리즘은 파이썬에서 heap을 이용해 구현할 수 있다. 보통 최소 힙으로 정렬이 되기 때문에 최단 경로를 찾을 때 유..
알고리즘 기록
2022. 3. 27. 16:16