728x90 반응형 Floyd-warshall1 [Algorithm] 최단 경로 탐색(Shortest Path) - 플로이드 워셜 알고리즘(Floyd-Warshall Algorithm) 개요 ◎ 플로이드 워셜 알고리즘이란? ◎ 그림 예시 ◎ 구현 코드 (Java) ◎ 시간 복잡도 ◎ 다익스트라 알고리즘과 비교 안녕하세요. J4J입니다. 이번 포스팅은 플로이드 워셜 알고리즘에 대해 적어보는 시간을 가져보려고 합니다. 플로이드 워셜 알고리즘이란? 플로이드 워셜 알고리즘은 정점들 간의 최단 경로를 탐색하기 위한 알고리즘 기법으로 시작 정점과 도착 정점 외에도 중간 정점을 선택하여 최소 거리를 탐색하는 방법을 사용합니다. 예를 들어 A, B, C, D, E 정점이 있다고 가정하면 다음과 같이 탐색을 합니다. 1-1. 중간 정점을 A로 선택합니다. 1-2. 모든 정점들 간의 거리를 중간 지점인 A를 거쳐서 가는 거리와 비교하여 최솟값들을 저장합니다. 2-1. 중간 정점을 B로 선택합니다. 2-2.. 2021. 2. 1. 이전 1 다음 728x90 반응형