플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm) 플로이드-워셜 알고리즘은 그래프에서 모든 정점 간의 최단 거리를 구하는 알고리즘입니다. 데이크스트라 알고리즘이 하나의 정점(시작 정점)으로부터 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이었다면, 플로이드-워셜 알고리즘은 모든 정점에서 모든 정점으로부터 모든 정점까지의 최단 경로를 구하는 알고리즘이며 음의 경로가 존재하는 그래프에서도 사용할 수 있습니다. 또한 플로이드-워셜 알고리즘은 다이나믹 프로그래밍 기법이 적용될 수 있습니다. 알고리즘 원리 플로이드-워셜 알고리즘은 정점 A에서 정점 C에 대한 최단경로를 구하기 위해 `정점 A에서 정점 C에 대한 경로`와 `정점 A에서 정점 B를 거쳐 정점 B에서 정점 C로 가는 경로`를 ..