백준 1753번 최단경로

< 백준 1753번 최단경로 - 마포 코딩박 >

사용한 알고리즘: 다익스트라


 시작 정점 K에서 각 정점까지의 최단 경로의 경로값을 출력하는 문제였습니다. 저는 다익스트라를 이용해 해결하였습니다.

문제풀이는 다음과 같습니다.

(1) (코드 13~19)
 시작정점 K에서 < i번 정점까지, w의 경로값만큼 걸린다 > 를 저장할 pq를 만듭니다.
 경로값이 작은게 위로 오게 만듭니다.

(2) (코드 30~50)
 시작정점 K를 제외한 나머지 정점까지의 경로값을 모두 Infimum으로 바꾸고 시작합니다.
 pq에는 초기에 < K(자기자신), 0(경로값=0) > 을 넣고 시작합니다.
 pq에서 하나씩 빼보며, 해당 정점과 연결된 정점들의 경로값들을 최신화해줍니다.