Dev On The Coffee Dev On The Coffee

# 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) 1. 플로이드 워셜 알고리즘 개요 플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)은 최단 경로를 구하는 또 하나의 대표적 알고리즘이다. 다만, 다익스트라 알고리즘이 '한 지점에서 다른 특정 지점까지의 최단 경로를 구하는 경우'에 사용한다면, 플로이드 워셜 알고리즘은 '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구하는 경우'에 사용한다. 플로이드 워셜은 다익스트라처럼 단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행하지만 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 없다. 그리고 2차원 테이블에 모든 노드의 최단 거리 정보를 저장하며, 이를 점화식을 통해 갱신한다는 점에..