플로이드 워셜 (1) 썸네일형 리스트형 플로이드-와샬(Floyd-Warshall) 알고리즘 이해하기 최단경로를 탐색하는 플로이드-와샬(Floyd-Warshall) 알고리즘에 대해 알아보자.플로이드-와샬 알고리즘은 그래프에서 모든 정점 쌍 간의 최단 거리를 찾는 동적 프로그래밍(Dynamic Programming) 알고리즘이다. (만약 최단거리의 경로를 구하고 싶다면 복원 로직의 추가가 필요하다.)1. 동작방식의 이해플로이드-와샬 알고리즘의 동작 방식은 아주 간단하다.모든 정점 쌍(i,j)에 대해, 중간 정점 k를 경유하는 경로가 기존 경로보다 짧은지 검사각 단계에서 k번째 정점을 거쳐가는 모든 경우를 고려즉 아래와 같은 세 노드가 있을 때, 기존에 주어진 i → j 의 길이와 노드 k가 중간에 추가된 i → k → j 를 비교하여 i → j 의 길이를 더 작은 값으로 갱신하는 것이다.점화식은 아래와 같.. 이전 1 다음
