Floyd-Warshall's Algorithm (1) 썸네일형 리스트형 [Algorithm] Floyd-Warshall's Algorithm (플로이드-와샬 알고리즘) 1. Floyd-Warshall's Algorithm 플로이드 와샬 알고리즘은 모든 정점간의 최단 거리를 구하는 All pairs shortest path solving 알고리즘이다. 플로이드 와샬 알고리즘은 거쳐가는 정점을 기준으로 최단 거리를 구한다. 두 정점의 최단 거리를 구할 때 다른 모든 정점을 후보로 각 정점들을 거쳐갈 때의 거리를 비교하여 최소가 되는 경로를 찾는다. 소스 코드를 보면 가장 간단한 알고리즘이다. 2. 플로이드 와샬 알고리즘 구현 플로이드 와샬 알고리즘은 모든 정점 쌍에 대해서 다른 정점들을 중간 경로로 거치는 경로의 거리를 비교하여 최단 거리를 구한다. 1) 먼저 현재 그래프의 간선들을 기준으로 각 정점간의 거리를 저장할 행렬을 초기화한다. 2) 중간 경로가 될 정점을 선택한.. 이전 1 다음