pq에 넣을 때는

• operator 연산자를 만들어주는데,
  타입을 반드시 이렇게 const 로 해야 오류 발생하지 않음.

비교 연산자에 대해서

• 이렇게 하면 오류발생하는데 , pq의 디폴트는 operater<() 이기 때문이다.

• 그래서 위의 operator<() 를 사용하고 싶다면, pq의 비교값설정을 greater로 변경하면 됨.
  

=> 즉 pq의 디폴트는 less라는 것이다.

주의할점

• greater가 디폴트값이다.
  

---

다익스트라

• 일단 이 문제의 시작정점은 1번이다.

코드에 대해서 주의할점

• pq 초기화
  : 시작정점에 연결된 node를 넣는 것이 아니라,
  시작정점의 번호와 가중치 0을 넣고 시작하는 것이다.
  

• 위의 방식대로 하게 되면, 시작정점 처리가 되는 것이 아니고,
  연결되어 있는 2번과 4번부터 진행한다.
  

• 올바른 코드
  : 시작정점만 pq에 넣고 시작하자.
  

visited 에 대해서

• bfs 구조와는 다르다.
  : bfs는 동일한 가중치이고, 다익스트라는 다른 가중치이다.

• 방문 처리를 여기서 하고 있다.
  

지금 우리는 pq에 가중치가 가장 작은 값부터 처리를 하는 것이므로, pq를 빼는 순간 nextV는 이미 처리된 정점이다.

• 예를 들어 a->c : 5 // a->b->c : 10 가 있다고 하자.
  그렇다는 것은 a-> c : 5 이고, a->b : 4, b->c : 6 이라고 한다면, pq 입장에서 생각해보면, 굳이 a->b->c 갈 필요도 없이 a->c에서 최단값 구했기 때문에 visited[c] = true 된다는 것이다. 여러군데 걸쳐서 진행할 필요도 없다.

• 그런데 왜 여기서는 하지 않지? 생각할 수 있다.
  : 여기의 코드는 연결된 정점간의 우선순위가 정해져 있지 않기 때문에 그냥 pq에다가 값을 넣어주는 부분이다.
  그러니까. vertex[a][c] 즉 , c에 연결된 다음 정점들에 대해서 pq에 넣어주는 것이므로, visited 를 체크하거나, 방문처리하면 안된다.
  

• 결론
  : 여태껏 계속 bfs 문제만 풀어와서 visited 체크하고 방문ok를 하는 부분이 다르다. 생각하는데, 정말 다르게 해야 한다.
  => 다익스트라는 pq 우선순위이기 때문에 가장 낮은 가중치의 정점을 나오자마자 visited 방문처리를 반드시 해야 한다.

visited왜 반드시 해야해??

-> visited를 사용하지 않으면, 이미 처리된 정점에 대해 연결된 상황이 있으면 , 이미 dist 계산이 완료되었지만, 또 진행하기 때문이다.