이것 저것 뚝딱거리는 사람 이것 저것 뚝딱거리는 사람

플로이드-워셜(Floyd-Warshall) 알고리즘 그래프의 모든 노드 간 최단 거리를 구하는 알고리즘이다. 시간 복잡도는 $O(n^3)$이므로 모든 최단 경로가 필요하지만 노드의 수가 적을 때 사용할 수 있다. 아이디어 한 노드(k)가 다른 두 노드(a, b)의 중간지점이라 생각한다면, a에서 b로 가는 경로는 $a-k-b$ 이다. (k가 a혹은 b라면 경로는 a-b가 된다.) $a-k-b$를 모두 조사한다면 a-b간 최단 경로를 알 수 있다. 아래와 같은 그래프를 가정하면 2를 중간 노드로 둘 경우, 2-2-3, 2-2-5, 3-2-5의 세 가지 경로의 값을 알 수 있다. 이 값들 중에서 3-2-5의 경우 3-5로 가는 경로보다 값이 작으므로 업데이트 해준다. 코드 for k in range(1, n..