플로이드 워셜(Floyd-Warshall) 알고리즘이란 무엇인가?

모든 노드에서 다른 모든 노드까지의 최단 경로를 구하고자 할 때 사용하는 알고리즘입니다. 다익스트라 알고리즘과 마찬가지로 거쳐 가는 노드를 기준으로 알고리즘을 수행합니다. 2차원 테이블에 최단 거리 정보를 저장합니다. O(N^3) O(N3)의 시간복잡도를 가집니다. 각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인합니다. D_{ab} = min(D_{ab}, D_{ak} + D_{kb})...

그래프알고리즘워셜플로이드GraphalgorithmShortest Pathfloyd-warshall플로이드워셜최단경로Graph