Dijkstra Algorihm

== 최단경로검색 Dijkstra Algorithm == 

	- Find Shortest Path    - Weighted graph를 볼 수 있다. 표를 작성하는데!!
	1. A에서 출발한다고 하고, A와 연결된 node들의 cost(비용)와 어디에서 왔는지 첫번째 줄에 적어준다.   2. C가 가장 cost가 적기 때문에 C를 두번째 줄에 적어준다. C node와 연결된 node는 A를 제외하고 E가 있다. E까지 가는데 누적 cost가 3이기 때문에 3과 이전노드 C를 적어준다. 나머지 빈칸은 copy over 해준다.    3. 2번째 줄에서, C노드를 제외하고 가장 최소의 cost를 보니 B와 E가 있는데, B를 보겠다.  4. 3번째 줄에 B를 적어주고,  2번의 과정을 반복해 준다. 단, 이전 cost보다 큰 누적 cost가 발생한 경우에는 위의 값을 그냥 그대로 copy over 해준다.   5. 마지막까지 위와 동일하게 반복해 준다!!
	- Back tracing을 통해서 최단경로를 알 수 있다.   - Stack이 필요하다.   - 도착지 부터 넣어주네!! 차근차근 넣고, 전부타 pop 해주면 그게 최단경로이다!!

 

- Dijkstra 어디에 쓰이나?

  - GPS 프로그램 구현

source-code : The-G

reference : 상상개발자