핵심 아이디어
- 모든 정점 ~ 모든 정점으로 최단 경로 구할 때 사용
- 거쳐가는 정점을 기준으로 최단 거리를 구하기!
코드
// k = 거쳐가는 노드, i = 출발 노드, j = 도착 노드
for(int k=0; k<N; k++)
{
for(int i=0; i<N; i++)
{
for(int j=0; j<N; j++)
{
if (d[i][j] > d[i][k] + d[k][j])
d[i][j] = d[i][k] + d[k][j];
}
}
}