wonseok.log wonseok.log

이 글은 (https://m.blog.naver.com/ndb796/221234424646) 블로그 글을 참고하여 작성하였습니다. 다익스트라 알고리즘 다이나믹 프로그래밍(DP)을 활용한 대표적인 최단 경로 탐색 알고리즘입니다. 기본적으로 다익스트라는 하나의 최단 거리를 구할 때 이전에 구했던 최단 거리를 사용한다는 특징때문에 다이나믹 프로그램을 활용한다고 볼 수 있습니다. 출발 노드를 설정합니다. 출발 노드에서 각 노드까지 가는 최소 비용을 배열을 만들어 저장합니다. 방문하지 않는 노드 중에서 가장 비용이 적은 노드를 선택합니다. 해당 노드를 거쳐서 각 노드로 가는 경우까지 비교하여 최소 비용을 갱신합니다. 위 과정에서 3~4번 반복합니다. 여기서 3번 과정에서 코딩 구현 시 배열을 완전 탐색해서 최소 ..