다익스트라 알고리즘

별거업다.
그래프다. 그래프를 트리로 바꾸면 중복해서 노드를 방문한다. 제일 좋은 가중치만 남겨둔다.

트리를 순회하는 방법은 너비우선, 깊이우선, 레벨우선탐색, 등등? 있다. 

그중에 하나인 너비우선탐색을 해서 설명하겠다.

출발지부터 목적지까지 너비우선탐색을 한다.
한 노드를 처음방문하면 값을 초기화한다.
다음에 또 그 노드를 방문하면 가중치를 비교한 후 더 좋은 놈을 선택하면 된다.
나중에는 제일 좋은 가중치만 존재하게된다.