floyd-warshall

[Algorithm] 플로이드 워셜 (Floyd-Warshall) 알고리즘

Floyd-Warshall Idea 플로이드-워셜 알고리즘은 모든 정점에서 다른 모던 정점까지의 최단 경로를 모두 구하는 알고리즘입니다. 모든 정점에서 다른 모든 정점까지의 최단 거리를 저장해야 하기 때문에 2차원 테이블에 최단 거리 정보를 저장합니다. 경로 계산 방식에는 아래와 같은 종류가 있습니다. 1. (One-To-One) 한 지점에서 다른 특정 지점까지의 최단경로 구하기 2. (One-To-All) 한 지점에서 다른 모든 지점까지의 최단경로 구하기 3. (All-To-All) 모든 지점에서 모든 지점까지의 최단경로 구하기 플로이드 워셜 알고리즘은 이 중 3번째 유형(All-To-All) 입니다. 플로이드 워셜 알고리즘의 점화식은 아래와 같습니다. 3중 반복문을 이용하여 위 점화식을 기준으로 테이..