플로이드-워셜 모든 노드간의 최단 경로를 구할 수 있는 알고리즘 입니다. 다익스트라는 출발 지점이 정해진 경우에 사용할 수 있지만 플로이드-워셜 알고리즘은 한번 실행으로 모든 노드간의 최단 경로를 구할 수 있습니다. 대신 $O(n^3)$ 이라는 시간 복잡도를 가지고 있습니다. 그래프내에 음의 간선이 있는 경우에도 활용 가능합니다. 해결 방법 그래프가 주어지면 각 간선을 토대로 2차원 인접행렬을 만듭니다. 알고리즘은 여러 라운드로 구성됩니다. 각 라운드마다 경유 노드를 지정하고 해당 노드를 반드시 지나는 경우와 기존의 경우를 비교하여 더 짧은 경우를 선택합니다. 모든 노드를 경유하는 경우를 고려해야 하므로 노드의 개수가 n 이라면 n개의 라운드를 반복합니다. 예시를 들어 알아봅시다. 위의 그래프를 2차원 ..
