Floyd-Warshall
-
Floyd-Warshall알고리즘 2020. 3. 17. 15:29
그래프에서 정점끼리의 최단 경로를구하는 문제 중다익스트라에 이어 플로이드 워셜 알고리즘에 대해 알아보도록 하자. Floyd-Warshall Algorithm 플로이드 워셜 알고리즘개념 : 모든 정점끼리의 최단 거리를 구하는 알고리즘(다익스트라가 한 정점에서 다른 정점들까지였다면, 플로이드는 모든 정점들을 다 구하는 방법이다.)(각 정점을 시작점으로 다익스트라 알고리즘을 반복하여도 되지만, 플로이드는 단 한번의 시행으로 모든 쌍을 구할 수 있다.)속성 Optimal substructure - 최단 경로의 부분경로는 역시 최단 경로다. (특정 경로 안에 무수히 많은 경로가 있을 때, 중간 정점들이 각각 최단이 된다면 이를 모두 이은 경로 또한 최단이 된다는 개념)작동 방식- 정점(1,2, … , k) 이 있..