플로이드 워셜_FloydWarshall

플로이드 워셜

• 모든 지점에서 다른 모든 지점까지의 최단 경로를 구하는 알고리즘
• 단계마다 ‘거쳐가는 노드’를 기준으로 알고리즘을 수행한다. 하지만 매 단계마다 방문하지 않은 노드 중에서 최단거리를 갖는 노드를 찾을 필요가 없다.
• 2차원 테이블에 최단 거리 정보를 저장한다.
• DP알고리즘에 속한다
• 노드 개수가 N이라고 할 때, N번만큼의 단계를 반복하며 ‘점화식에 맞게’ 2차원 리스트를 갱신하기 때문에 DP라고 볼 수 있다.
• 시간복잡도 O(N^3)