All-Pairs Shortest Path 무방향 그래프, 웨이트 있음. 가능한 모든 최단 거리 쌍 찾기. 다익스트라 n번 돌리기? ⇒ O(n*(m+n)logn) Floyd Warshall - O(n³) D[k][i]][j] 를 구하자. ⇒ 반복문 세번 O(n³) D[k][i]][j]는 1, 2, 3, …, k 노드를 거치는 i → j 의 가장 짧은(최단) 거리. 1, 2, 3, …, k 노드를 전부 거칠 필요는 없고, 단지 i, …, j 사이에 거칠 수 있는 노드로 1, 2, 3, …, k 가 존재한다는 의미. 또한 D[k][i][j] 에서 k+1, k+2, … ,n 노드는 사용하지 않음. k = n 일 때가 i → j 최단 거리의 최종 답. k = 0 일 때는 i → j 의 기본 웨이트와 같다.(다른..