1. 문제정의 모든 노드 쌍들마다의 최단경로 구하기 (path까지는 어렵기 때문에 길이만 구할 것이다) undirect 그래프라고 가정. 가장 쉬운방법은 다익스트라 알고리즘을 n번 돌리는 것이다. 2. Floyd Warshall Alg 각 노드별로 번호를 부여했다고 가정하자. i → j로 가는 최단경로를 구할 건데, {1, 2, ..., k}번 노드 중에서만 거쳐가는 최단 경로를 찾으면 된다. 이 과정을 k가 0부터 N까지 반복한다. (k가 n일 때가 최종 답이된다,) 즉, 구하고자 하는 것은 모든 (i, j) 쌍에 대하여 1번부터 k번 노드 중에서만 거쳐서 갈 수 있는 최단경로이다. k=0이라면 {공집합}이고 i와 j를 연결하는 것은 direct edge밖에 없다. direct edge가 없다면 답은 ..