Floyd-Warshall의 k번째 반복에서 D[i][j]를 D[i][k]+D[k][j]와 비교하는 상태 의미는 무엇인가요?

k번째 단계의 D[i][j]는 중간 정점으로 1..k만 허용했을 때 i에서 j로 가는 최단 비용이라고 설명할 수 있습니다. 정점 k를 새로 허용하면 더 좋아진 경로는 k를 거쳐 i→k와 k→j로 나뉘므로 기존 D[i][j]와 D[i][k]+D[k][j]를 비교합니다. 새 경로의 두 부분 역시 k 이전 단계의 의미를 사용해야 하므로 바깥 루프는 k여야 합니다.

예를 들어 직접 1→4=10, 1→2=2, 2→4=3이라면 정점 2를 허용한 단계에서 D[1][4]가 10에서 5로 바뀝니다. 정점 3을 허용해 1→3=8, 3→4=1을 비교해도 9라서 5가 유지됩니다. 표의 값은 단순한 “현재까지 찾은 경로”가 아니라 허용 중간 정점 집합으로 의미가 고정된 상태입니다.

초기 대각선은 D[i][i]=0, 직접 연결이 없으면 INF입니다. 두 부분 중 하나라도 INF이면 합을 계산하지 않아야 하고, 큰 비용이면 checked addition을 적용합니다. in-place 갱신도 같은 k를 고정한 동안 이 의미를 보존하므로 i,j 순서는 안쪽에서 처리해도 되지만 k 순서를 바꾸면 상태 불변식이 깨질 수 있습니다.

in-place 안전성은 k를 고정하는 데서 나옵니다. k=2일 때 D[1][2]가 이미 더 좋아져도 그 경로의 중간 정점은 여전히 허용 집합 1..2 안에 있고, D[2][4]의 갱신도 같은 집합 안에 있습니다. 따라서 둘을 이어도 k 이후 정점을 몰래 사용하지 않습니다. 반면 i나 j를 바깥으로 바꾸면 한 셀에서 이미 더 큰 단계의 값을 다른 셀이 읽을 수 있어 D_k와 D_{k-1}의 의미가 섞입니다. INF 한쪽을 합산하지 않고 checked addition을 적용해야 하며, next metadata는 거리 갱신과 같은 분기에서 바꿔야 합니다.