플로이드 워셜

[Algorithm/Python] 플로이드 워셜 알고리즘이란?

들어가며 본 포스팅은 플로이드 워셜 알고리즘에 대해 소개합니다. 📌 플로이드 워셜 알고리즘 플로이드 워셜(Floyd-Warshall) 알고리즘이란, 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 사용하는 알고리즘입니다. 기존에 소개된 다익스트라 알고리즘에서의 최단 거리 테이블에서 거리가 가장 짧은 노드를 탐색해야 했던 과정을 생략할 수 있다는 점이 차이점입니다. 모든 노드가 다른 노드로 가는 최단 거리의 정보를 2차원 리스트에 담아 저장합니다. 노드의 개수 N만큼 점화식에 맞게 2차원 리스트를 갱신하므로 다이나믹 프로그래밍으로 볼 수 있습니다. ☑️ 시간 복잡도 모든 최단 경로를 2차원 리스트에 담아 처리하므로 매번 $O(N^2)$의 시간이 소요되며, 노드의 개수 N만큼 $O(N..