국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다 Shortest Paths Shortest Paths란 말 그대로 두 점 사이의 최단 경로임 => 두 점 사이의 경로 중 비용이 최소인 경로(경로 내 간선들의 비용 합) Single Source Shortest Paths 그럼 이번 포스팅의 주제인 Single Source Shortest Paths는 뭘까? 이는 한 점과 다른 모든 점 사이의 최단 경로를 의미함 => 시작 정점 (source node) s에서 다른 모든 점까지의 최단 경로 찾기가 곧, s가 root인 shortest-path tree 찾기임(일종의 spanning tree라고 볼 수 있음) Dijkstra's Al..
