다익스트라 알고리즘.

설명 잘 된 블로그 : http://kks227.blog.me/220796029558

블로그에 나온 것처럼 그래프에서 어떤 정점에서 다른 정점으로 갈 경우 최소값을 구하는 알고리즘이다.

다익스트라 알고리즘은 모든 비용이 음수가 아닐 경우에만 동작한다.

시간 복잡도 : O(|E|lg|V|) (정점 V, 간선 E)

그림은 위의 블로그에서 퍼왔다.

1. 정점 0이 시작점이고 여기서 출발하여 다익스트라로 각 점까지의 최솟값을 구한다고 하자.

각 점까지의 거리는 초기치를 무한대로 설정해놓는다.

2. 첫 정점에서 갈수 있는 점들을 큐에 저장해놓고 가장 비용이 적은 점부터 방문한다. 

방문후 비용을 초기화해준다.

3. 다음 시작점중 비용이 가장 적은 1부터 방문한다. 왜 비용이 적은것부터 방문하냐면, 아래 그림의

3이 우리의 최종 목표라고 가정하자. 그냥 갈수 있는 모든곳을 큐에 넣고 빼는식으로 방문한다고 하면

점 2에서 3을 방문할수도 있고, 1에서 3을 방문할수도 있다. 그런데 1에서 3을 먼저 방문하게 되면

비용이 22로 2에서 3을 방문하는 20보다 크다. 결국 방문하지 않아도 되는데 낭비가 되버린다. 그러므로

가장 작은 비용부터 방문한다. 이걸 위해 우선순위 큐를 사용할수 있다. http://qkqhxla1.tistory.com/663

이런식으로 하나하나 다 방문후 값을 초기화해준다. 마지막에 초기값인 무한대가 남아있으면

방문하지 못하는 곳이다.