[C++] 다익스트라 dijkstra

📕 다익스트라

• 노드 간 최단 거리를 구하는 알고리즘
• 가중치를 통해 가장 가까운 거리의 노드의 방문을 반복하며 갱신

📚 진행 순서

1. 아직 확정하지 않은 점들 중에서 가장 짧은 거리(시작점으로부터)로 갈 수 있는 점 선택
2. 해당 점에서 갈 수 있는 모든 점들에 대한 거리를 갱신

다익스트라로 최단거리를 구하면 안되는 경우

• 가중치가 "음수" 일 때 음수 싸이클이 발생하여 무한 반복

💻 구현 방법

1. for문
2. priority queue 활용
   -> 어떤 우선순위를 정하고, 해당 우선순위대로 data를 꺼내 사용
   -> for문에서 사용한 우선순위 이용

// 1. for문
		int now; // <- 이번에 확정할 점(시작점으로부터 가장 가까운 점)
		int mindist = 1e9; // 지금까지 본 (확정되지 않은 거리중 최단 거리)
		for (int i = 1; i <= cntNode; i++) {
			if (dist[i] < mindist && used[i] == 0) {
				mindist = dist[i];
				now = i;
			}
		}
        
// 2. priority queue
	struct now = pr.top();
    mindist = now.dist;
    node = now.node;