시간 복잡도
공간 복잡도
// 플로이드-워셜 알고리즘 실행
for (int k = 1; k <= N; k++) {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if(arr[i][j] > arr[i][k] + arr[k][j]) {
arr[i][j] = arr[i][k] + arr[k][j];
}
}
}
}
k
에 대해, 모든 정점 쌍 (i, j)
의 거리를 검토하고,i
에서 k
를 거쳐 j
로 가는 경로가 기존의 i
에서 j
로 가는 경로보다 짧은지 비교합니다. 만약 더 짧다면, 해당 경로의 거리로 업데이트합니다.if(arr[i][j] > arr[i][k] + arr[k][j]) { arr[i][j] = arr[i][k] + arr[k][j]; }
arr[i][j]
의 기존 경로가 k
를 거쳐서 이동할 때의 거리보다 짧을 경우 갱신한다.
i -> k -> j
로 이동하니까 중간에 k
를 다리로 이용한다고 생각
[i][k]
-> [k][j]
각 중간에 k
가 들어간다.