floydwarshall

플로이드 와샬(Floyd Warshall)

📔 플로이드 와샬(Floyd Warshall) 란 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 모든 꼭짓점 사이의 최단 경로의 거리를 구하는 알고리즘이다. 음수 가중치를 갖는 간선도 순환만 없다면 잘 처리된다. 제일 바깥쪽 반복문은 거쳐가는 꼭짓점이고, 두 번째 반복문은 출발하는 꼭짓점, 세 번째 반복문은 도착하는 꼭짓점이다. 이 알고리즘은 플로이드 알고리즘이라고도 알려져 있다. ( 출처: 위키백과 ) 모든 정점에서 모든 정점으로의 최단 경로를 구하는 것! 거쳐가는 정점을 기준으로 구한다. 다이나믹 프로그래밍 기법을 이용 다익스트라의 경우 한 정점에서 모든 정점까지 의 최단 경로 반복문이 3개이므로 시간복잡도는 O(N^3) 이다. 하지만 코드는 매우 간단하다. 📔 플..