플로이드 워셜1 최단 경로 찾기 : 플로이드 워셜(Floyd-Warshall) 알고리즘 들어가며 오늘 살펴볼 알고리즘은 지난번에 살펴봤던 다익스트라 알고리즘과 마찬가지로 최단경로를 찾는 알고리즘 중 하나인 플로이드 워셜(Floyd-Warshall) 알고리즘입니다. 같은 목적을 가진 알고리즘이라 그런지 익숙하게 느껴지는데, 플로이드 워셜은 어떤 방법을 통해서 최단경로를 구하는지 살펴보도록 하겠습니다. 알고리즘 플로이드 워셜 알고리즘은 동적 계획법을 활용한 길찾기 알고리즘입니다. 다익스트라가 지금까지 방문한 지점에서 가장 짧은 거리에 있는 지점을 차례로 선택하여 길을 찾아가는 반면, 플로이드 워셜은 지점들 중 하나를 선택해 두 지점을 연결하는 경로 중 해당 지점을 경유하는 가장 짧은 거리를 갱신하여 저장하는 과정을 반복해 길을 찾아가는 방법입니다. 로직으로 만들기 쉽게 단계별로 살펴보면, 경로.. 2023. 5. 21. 이전 1 다음