Dijkstra2 [MIT 6.006 정리] Lec 18. 그래프 (최단 경로 알고리즘_ 다익스트라 가속화) * 본 포스팅은 기본적으로 edwith 플랫폼을 통해 제공되고 있는 MIT 6.006 Introduction to Algorithms (Fall 2011) 강의 내용을 바탕으로 정리한 것입니당 :D ------- * ------- * ------- * ------- * 단일 시작 단일 도착 다익스트라 이전까지 일반적인 최단 경로 알고리즘 (다익스트라 / 벨만-포드 등) 은 '하나의 시작점과 임의의/모든 도착점에 대해 최단 경로를 구하는 문제 (single-source, any/all destination)' 를 가정했음 하지만 모든 도착점이 아닌 특정한 하나의 도착점에 대해서만 최단 경로를 구하면 되는 문제라면, 몇 가지 최적화를 통해 알고리즘 실행 시간을 줄일 수 있음! 최악 시간 복잡도는 변하지 않으.. 2021. 3. 30. [MIT 6.006 정리] Lec 16. 그래프 (최단 경로 알고리즘_ 다익스트라 알고리즘) * 본 포스팅은 기본적으로 edwith 플랫폼을 통해 제공되고 있는 MIT 6.006 Introduction to Algorithms (Fall 2011) 강의 내용을 바탕으로 정리한 것입니당 :D ------- * ------- * ------- * ------- * 최단 경로 알고리즘의 기본 구조 Recap d[v] : 출발점 s 부터 정점 v 까지의 (현재 시점에서의) 최단 경로의 길이 d[s] = 0, d[v] = inf. (for any v) 로 초기화 후, 완화(relaxation) 과정을 통해 d[v] 값을 줄여 나감 모든 정점 v 에 대해 d[v] = delta[v] (출발점에서 해당 정점까지의 실제 최단 경로(a shortest path) 의 길이) 로 수렴할 때까지 반복 후 알고리즘 종.. 2021. 3. 17. 이전 1 다음