CS/알고리즘 이론
[알고리즘] 최단 경로 문제(Shortest Path Problem)
1. 최단 경로의 이해 먼저 최단 경로의 기본 성질에 대해 파악해보자. u → v : 노드 u에서 노드 v로의 하나의 엣지로 구성된 경로 s ⇝ v : 노드 s에서 v로의 경로를 표 시하고, 중간에 여러 노드가 존재 가능 s ⇝ u → v 인 경우, 이 경로에서 u는 v의 predecessor 또는 parent이다 만약 s ⇝ u → v 가 s에서 v로의 최단 경로 중 하나라면, s ⇝ u 역시 s에서 u까지의 최단 경로 중 하나이다. s에서 v까지의 여러 경로 중에서 u를 통해 v에 도달하는 경로중에 최단 경로가 있다는 의미이고, s ⇝ u를 먼저 계 산하여 알고 있다면, s ⇝ u → v는 쉽게 계산할 수 있다. dist[v] = "s에서 v까지의 최단 경로의 길이"라고 정의하면 다음과 같은 식이 성..
