[일반] 왜 플로이드 와샬 알고리즘에서 경유지점이 루프 바깥에 위치하나용

[익명(117.111)]

코드를 아무리 봐도 이해 안가는데
중앙이나 안쪽에 위치하면 안되는 이유가 먼가영 ㅠ

[Gravekper(gravekper)]

몇개 노드를 거치는 어떤 가상의 최단 경로를 가정하고 루프를 다 돌면 그게 반드시 만들어진다는 증명을 해보는 방향으로 읽어봐

[익명(175.119)]

증명을 모르는데 코드를 봐보았자 어케 알리오

[pichulia(211.36)]

가장 바깥 for문이 경유지를 의미하는게 아님.

[익명(117.111)]

맞지않음? i -> k -> j 면 최상단에 k루프 그 안에 i루프 그 안에 j루프 일케되지 않나?

[pichulia(211.36)]

저 k가 '나 k 지나갈거임' "만"을 의미하는게 아님. 코드만 보면 d[i][j] = d[i][k]+d[k][j] 이지만 증명을 보면 그 안에 d[k][i][j] = d[k-1][i][k] + d[k-1][k][j] 라는 의미가 숨어있는걸 알 수 있음