Floyd-Warshall Algirithm (플로이드 워셜 알고리즘)

플로이드 워셜 알고리즘이란? 플로이드 워셜 알고리즘은 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다. 이전에 배웠던 다익스트라 알고리즘은 한 노드에서 가능한 모든 노드 쌍에 대해 최단 거리를 구했기 때문에 이 점이 2가지의 알고리즘에 차이라고 할 수 있다. 플로이드 워셜 알고리즘의 시간 복잡도는 O(N³)으로 3중 for문으로 보통 모든 경우의 수를 비교한다. 플로이드 워셜 알고리즘의 핵심은 거쳐가는 정점을 기준으로 최단 거리를 구하는 것이다. 그래서 k를 두어서 모든 노드에 대해서 최단 거리를 구할 수 있도록 하였다. fun floydWarshall() { val d = Array(4) { IntArray(4) } for (i in 0 until 4) { for (j in 0 ..

원문링크 : Floyd-Warshall Algirithm (플로이드 워셜 알고리즘)