https://blog.naver.com/ndb796/221234424646
위의 블로그 글과 위키백과를 참고하였습니다.
지금 푸는 문제에 다익스트라 알고리즘이 필요해서 정리해 두기로 했따!
최단 경로 문제를 해결하는 데 자주 사용되는 알고리즘이기 때문에 잘 알아놔야 한다. 앞서 설명한 플로이드-와샬과는 다르게 다익스트라 알고리즘은 '하나의 정점'에서 모든 정점으로 가는 최단경로를 찾을 때 사용하며, cost가 음수인 경우에는 제대로 된 결과값을 구할 수 없다.
플로이드-와샬과 마찬가지로 처음에는 현재 시점에서의 한 정점에서 다른 정점까지의 최소 비용을 저장한다. 한번에 갈 수 없는 곳은 infinite(아주 큰 값)으로 초기화한다.
그 후 방문하지 않은 정점 중 가장 비용이 적은 정점을 선택한 후 해당 정점을 거쳐서 가는 경우의 cost vs 기존의 cost를 비교하여 더 적은 값을 선택해가며 결과 테이블을 업데이트 한다.
모든 정점에 대해 해당 과정을 반복하면 모든 정점까지 cost가 가장 적은 경우를 구할 수 있다.
