graph(3) - 그래프의 최단 경로

다익스트라 알고리즘

하나의 정점 기준으로 모든 정점까지의 최단 경로를 아는 알고리즘입니다. 음수 가중치가 존재하지 않아야 합니다.

개선된 다익스트라 알고리즘을 사용해서 O(n*logn)의 시간 복잡도로 해결할 수 있습니다. 이를 사용하기 위해 우선순위 큐 자료구조를 사용합니다.

왜? continue 후 갱신 안하나요? 이미 if문에서 갱신을 했습니다. 그래서 최솟값들만 우선순위 큐에 넣었슴. 우순큐에서 나온 당시, 이미 최솟값이 저장되어 있다는 것임. 그래서 작다? 바로 폐기처분함.

이미 확정이 되어 버린 것임. 그래서 min으로 쓸 필요조차 없음 어차피 값이 같을 것이기 때문.