다익스트라 개념
하나의 노드에서 시작에서 각 노드들의 최단거리를 구한다.
다익스트라 로직의 특징은 아래와 같다.
1) 먼저 방문한 노드가 가장 최단거리임은 자명하다.
2) 방문한 노드에 연결되어 있는 다른 노드들을 다음 최단거리 노드의 후보로 저장할 수 있다(우선순위 큐에 저장). 하지만 이 후보 중 동일한 노드에 대해선 그 거리가 계속 갱신될 수 있다.
void dijkstra(int start) {
priority_queue<pair<int, int> > pq;
// 시작 노드를 pq에 먼저 삽입한다.
// 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
pq.push({0, start});
d[start] = 0; // d의 각 요소는 MAX_LEN으로 초기화된 상태
while (!pq.empty()) { // 큐가 비어있지 않다면
int dist = -pq.top().first; // pq의 디폴트는 Max Heap
int now = pq.top().second;
pq.pop();
// 현재 노드가 이미 처리된 적이 있는 노드라면 무시
// 이전에 먼저 방문한 노드가 최단거리를 갱신했음은 자명하다.
// 이 조건문은 이전에 방문한 노드와 동일한 번호의 노드가 후보 상에 존재할 때,
// 이를 없애는 것과 같다.
if (d[now] < dist)
continue;
// 현재 노드와 연결된 다른 인접한 노드들을 확인
for (int i = 0; i < graph[now].size(); i++) {
int cost = dist + graph[now][i].second;
// 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우 pq에 추가한다.
// 동일한 노드의 번호가 여러 개의 후보로 pq상에 존재할 수 있다. pq 자료구조의 특성으로 인해 그 중 거리가 더 짧은 것으로 먼저 pop 될 것이다.
// 이 조건문은 이전에 방문한 노드가 다시 한번 후보로 추가되는 것을 막는다.
if (cost < d[graph[now][i].first]) {
// (1) 최단거리 테이블 갱신
d[graph[now][i].first] = cost;
// (2) 후보로 추가
pq.push(make_pair(-cost, graph[now][i].first));
}
}
}
}