다익스트라
-
다익스트라(dijkstra) 최단 경로알고리즘/백준 2021. 8. 30. 17:55
풀이 다익스트라 알고리즘은 탐욕법과 동적 계획법을 같이 사용합니다. i 노드까지 최단 경로를 구하는 점화식 dist[i]가 등장하며 이를 구하기 위해 매번 최선의 선택(최소 가중치)을 수행합니다. 기본적인 흐름은 다음과 같습니다. 시작 노드를 방문하면서 시작합니다. 1. 방문한 노드에서 방문할 수 있는 다른 노드까지의 거리를 구합니다. 그 거리가 기존 값보다 짧으면 새로 갱신합니다. 2. 거리가 새로 갱신된 노드만 우선순위 큐에 넣습니다. 중복 방문을 없애기 위해서입니다. 이 외에도 중복 방문을 막기 위한 코드가 한 줄 더 있습니다. 3. 이 중에서 간선의 가중치가 최소인 노드를 방문합니다(우선순위 큐를 이용하면 최소 가중치를 쉽게 구할 수 있음). 4. 1번으로 갑니다. 코드 #include #incl..