최단 경로. [1753]

[1. 문제 설명]

방향그래프에서 edge 의 weight 가 주어질 때

시작점에서 그래프 내 모든 정점에 최단 거리로 방문할 때,

모든 정점의 최단 거리 값을 출력한다.

 

 

[2. 풀이 접근]

다익스트라는 우선순위 큐를 사용하여 구현 할 경우 그 시간 복잡도는 아래와 같다

O(V + ElogV) 이며,

여기서 E 는 Edge 의 개수, V 는 Vertex 개수 이다.

 

 

heapify 에 대하여

1. 처음 풀이에서 heapify 를 하여 우선순위를 재조정하는 코드가 있었다.
   => 힙에 이미 푸쉬되었지만, 다른 경로를 거쳐 오는 경우가 더 빠른 경우 가 발생할 수 있으므로
2. 실행시간이 다소 늦음
   => heap 에 푸쉬된 특정 정점을 찾기 위해 O(n) 에 시간이 걸리기 때문
   => heap 은 오름/내림 차순 등으로 정렬되지 않기 때문에,

heapify 가 필요 없는 이유

1. heap 에 이미 푸쉬되었지만, 다른 경로를 거쳐 오는 경우가 더 빠른 경우 가 발생 할 경우, 
   새로운 값으로서 heap 에 푸쉬하면 됨
2. 이 때, heap 이 재조정 되며,
3. 먼저 heap 푸쉬 된 값은 언젠가 pop 되지만, (1) 에서 푸쉬 된 값이 더 나은 경로를 형성하므로 
   자연스럽게 무시 됨 (=> 코스트가 더 높아서 인접한 정점으로 움직이지 못함)

 

[3. 코드]