- 플로이드 워셜 알고리즘
-모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산합니다.
-다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘 수행. (다만 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않음)
-2차원 테이블에 최단거리 정보를 저장
-다이나믹 프로그래밍 유형에 속함
노드의 개수와 간선의 개수가 적을때 사용
플로이드 워셜 알고리즘 코드 예시)
플로이드 워셜은 위와 같이 3중 for문을 사용하다보니 시간 복잡도가 O(N^3) n=노드의 개수 가 나온다. 따라서 노드와 간선의 개수가 적을때 사용 하도록 하자.
:)