봉황대 in CS

플로이드-와샬(Floyd-Warshall) 알고리즘 '거쳐가는 정점'을 기준으로 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘이다. ( ↔︎ 다익스트라 : 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘 ) 즉, (1) 정점 a에서 정점 b로 가는 최소 비용과 (2) 정점 a에서 정점 k로 가는 비용 + 정점 k에서 정점 b로 가는 비용을 비교하여 더 적은 비용을 가지는 쪽을 취하는 것이다. N개의 노드가 있을 때, N번만큼의 단계를 반복하여 점화식에 따라 2차원 리스트를 갱신하기 때문에 동적 계획법(Dynamic Programming) 알고리즘에 속한다. ( ↔︎ 다익스트라 : 탐욕(그리디) 알고리즘 ) * 동적 계획법(Dynamic Programming, D..