코딩못하는사람

단일 출발지 최단 경로( Single Source Shortest Path ) 하나의 출발점에서 각 정점까지 도달하는데 비용을 계산하여 최단경로를 구하는 것에는 두가지 다익스트라 알고리즘과 벨만-포드 알고리즘이 있다. 다익스트라와 벨만-포드의 차이는 음의 가중치를 다룰수 있냐 없냐의 차이이다.(벨만-포드가 가능) 다익스트라 알고리즘은 최소힙을 이용하여 구현할 수 있다. 우리가 알아볼 시작지점으로부터 다른 도착지점까지의 가중치 배열을 INF로 초기화한다.ans=[INF]*(v+1) 시작지점의 값을 0으로 초기화하고 heap에 (가중치,위치)을 넣어준다 while문을 사용하여 heappop을 통하여 최소값을 뽑아주고 뽑힌 (가중치+위치에 연결된 곳들의 가중치)로 연결된 곳들을 relax(경로가 더 효율적이면..