다익스트라 알고리즘

다이내믹을 활용한 최단 경로 알고리즘.

https://m.blog.naver.com/ndb796/221234424646

방법

1. 출발 노드 설정
2. 출발 노드 기준으로 각 노드의 최소 비용 저장
3. 방문하지 않은 노드 중 가장 비용이 적은 노드 선택.
4. 해당 노드 거쳐서 특정 노드로 가는 경우 고려하여 최소 비용 갱신.
5. 반복.

시간 복잡도

선형탐색으로 만들 경우 시간 복잡도가 O(N^2)이다. 단 힙 구조를 사용하여 시간 복잡도를 O(N*logn) 으로 만들 수 있다