k의 의미를 이해하지 못하고 있으신거 같아요.
플로이드-와샬 알고리즘은 i 부터 시작해서 j로 가는 경로중에 k를 거치는 경로들을 모두 구해서 dp로 푸는 것입니다.
11404번 - 플로이드
k의 의미를 이해하지 못하고 있으신거 같아요.
플로이드-와샬 알고리즘은 i 부터 시작해서 j로 가는 경로중에 k를 거치는 경로들을 모두 구해서 dp로 푸는 것입니다.
플로이드-와샬 알고리즘을 살펴보면
d[i][j] = min(d[i][j], d[i][k] + d[k][j]) 로 나와있습니다.
이를 다시 잘 살펴보면
i ~> k ~> j = min (i ~> k-1 ~> j, ( i ~> k-1 ~> k) + (k ~> k-1 ~> j)) 입니다.
즉, 모든 경로가 k - 1을 거치는것에 대해 업데이트를 해주고 k에 대해 dp를 적용하게 됩니다.
다시말해서 k - 1이 특정한 값으로 고정되어 있을 때 경로를 업데이트하고 k로 넘어간다는 의미입니다.
그런데 님 말씀대로 하면 k가 계속 바뀌므로 실패한다고 생각합니다.
댓글을 작성하려면 로그인해야 합니다.
ckddn1224 3년 전 1
지금 루프의 구조가 k - i - j 인데
distance[i][j] = Math.min(distance[i][j], distance[i][k] + distance[k][j]); 부분은 그대로 놔두고
루프를 i - j - k 순으로 하면 왜 틀린건지 모르겠습니다.. 관련 내용을 찾을수가 없어서 질문글 올립니다 ㅠㅜ