노트

이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강의를 듣고 정리한 내용입니다. Shortest Path(최단 경로)최단 경로 문제란 가장 짧은 경로에서 두 꼭지점을 찾는 문제로서, 가중 그래프에서는 구성하는 변들의 가중치의 합이 최소가 되도록 하는 경로를 찾는 문제이다.예를 들면, 도로 지도 상의 한 지점에서 다른 지점으로 갈때 가장 빠른 길을 찾는 것과 비슷한 문제이다. 이 때, 각 도로 구간에서 걸리는 시간을 변의 가중치라 할 수 있다.보통은 주어진 가중 그래프에서 (V는 꼭지점, E는 변, 가중치 함수 f : E → R)가 v에서 v'로 가는 모든 경로들 중 최소가 되도록 하는 경로를 찾는 문제이다.출처 : 위키백과 최단 경로 문제의 유형 - Single-Source : one to all하나..