플로이드

모든 쌍의 최단 경로를 구하는 알고리즘

d[k][i][j] : i 에서 j 로 가는 최단 경로, 중간에 방문할 수 있는 정점은 {1,2,....,k}

k가 경로에 없는 경우

d[k-1]][i][j] : k를 사용하지 않는 것이기 때문에

k가 경로에 있는 경우

i -> k 로 가는 최단 경로와 k -> j 로 가는 최단 경로중에는 중간에 절대 k 가 낄 수가 없다. 따라서
d[k-1][i][k] + d[k-1][k][j] 로 대신 바꾸어 쓸 수 있다.

따라서 결과값은 d[k][i][j] = min (d[k-1][i][j], d[k-1][i][k] + d[k-1][k][j]) 이다.

구현

이차원 DP 로 구현 가능하다. (배낭 문제 같이) k 가 없다고 해도 영향을 미치지 않는다.
(cf 배낭 문제 : d[i][j] i번 물건 , 무게 j 일 때 가치의 최대 , w[i], v[i]
d[i][j] =max (d[i-1][j], d[i-1]j-w[i]] + v[i]) -> 1차원 배열로 만들수 있다. (12865번))

for (int k=1; k<=n; k++) {
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
if (d[i][j] > d[i][k] + d[k][j]) {
d[i][j] = d[i][k] + d[k][j];}
}
}
}```