[Algorithm][다익스트라][boj]1753 최단경로

---

다익스트라 알고리즘 나무위키

시작점으로부터 갈 수 있는 모든 경로에 대한 최단거리를 구한다.

필요했던 것

- map : 간선정보를 저장할 map

- v : 이미 방문했는지를 위한 visit array

- d : 시작점으로부터 정점까지의 거리 정보를 가지고 있는 distance array

- pq : 현재 갈 수 있는(그리고 갈 수 있었던) 정점들을 담아 둘 priority queue. 정점과 거리 쌍으로 저장.

코드 가독성을 위해 pq에 첫 번째 위치 (시작점)을 미리 입력해 놓고 했음.

1. pq에서 하나 pop하고 이미 방문했던 곳인지 visit array 검사. 이미 방문했으면 다시 1번 반복.

2. 주변 경로 확인 후 map을 보면서 [원래 알고 있던 목적지까지의 거리]와 [현재 지점까지의 거리 + 목적지까지의 거리]를 비교 후 더 짧으면 갱신. 아직 등록되지 않았어도 갱신. 그 후 pq에 위치와 거리 쌍을 push

3. 이걸 우선순위 큐를 비울 때까지 반복.

같은 목적지로 가는 중복된 항목이 queue에 쌓일 수 있지만 어차피 1번 과정에서 빠르게 처리된다. 

오직 최단 거리일 때만 어딘가를 방문한다. 그러므로 이걸 걱정할 필요가 없다. 이미 방문했던 곳은 갱신하지 않는다.

view code on github