[Graph] 다익스트라

다익스트라 알고리즘? 그래프에서 노드들간의 최단 거리를 알아내기위해 사용하는 알고리즘이다. 다익스트라 알고리즘은 매우 직관적인 알고리즘이다. 그렇다면 다익스트라 알고리즘이 어떻게 동작하는지 알아보자. IDEA 예를 들어 아래와 같은 상황을 생각해보자. 위 와같은 지도를 보자. 집에서 각각의 상점까지의 최단거리를 알아내고자한다. 이때 다익스트라 알고리즘을 사용하여 해결해보자. 1. 처음 집에서 출발을 한다. 집에서 처음 출발할때, 가지고 있는 정보는 집에서 집으로 갈 때, 0이라는 시간이 소요된다는 것 뿐이다. 이제 집에서 바로 갈 수 있는 장소들에 대해 탐색해보자. 2. 집에서 바로 갈 수 있는 장소들 중 상점, 영화관, 은행의 경우 기존의 거리(INF)보다 집에서 집까지의 거리 + 집에서 각 위치들 까..

2019.09.18