for (int k = 1; k <= n; k++) { //경유지
for (int i = 1; i <= n; i++) { //출발지
for (int j = 1; j <= n; j++) { //도착지
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
k = 1 일 때, i -> j 와 i -> 1 -> j 중 작은 값이 dist[i][j]에 저장
k = 2 일 때, k = 1 에서 i -> j가 선택되었을 때와 i -> 2 -> j 중 작은 값, i -> 1 -> j가 선택되었을 때와 i -> 1 -> 2 -> j 중 작은 값 저장
...
이잖아요 근데 만약 i -> 2 -> 1 -> j 일때가 최단 거리이면 못 찾아야 하는거 아닌가요?
k=1 일 때 dp[2][j] := 2->1->j k=2 일 때 dp[i][j] := dp[i][2] + dp[2][j] = i->2->1->j
i->j로 갈 때 경로 상에서 가장 큰 번호를 k라 하면 k를 경유하는 최단경로 = (i에서 (1~(k-1)을 경유하며 k로 가는 경로) + (k에서 1~(k-1)을 경유하며 j로 가는 경로) = dist[i][k] + dist[k][j]. i->1->2->j는 1을 경유하는 (i->1->2)와 아무 것도 경유하지 않는 (2->j)로만 구성됨.