ckddn1224   3년 전

지금 루프의 구조가 k - i - j 인데

distance[i][j] = Math.min(distance[i][j], distance[i][k] + distance[k][j]); 부분은 그대로 놔두고

루프를 i - j - k 순으로 하면 왜 틀린건지 모르겠습니다.. 관련 내용을 찾을수가 없어서 질문글 올립니다 ㅠㅜ

wonkyum256   3년 전

k의 의미를 이해하지 못하고 있으신거 같아요.

플로이드-와샬 알고리즘은 i 부터 시작해서 j로 가는 경로중에 k를 거치는 경로들을 모두 구해서 dp로 푸는 것입니다.

ckddn1224   3년 전

wonkyum256 님 감사합니다. 

알고리즘 자체는 그렇게 이해하고 있는데, 정확하게 루프의 순서가 k - i - j 인지에 대한 설명을 못찾겠어서요.

i - j - k 일 경우 distance 배열이 갱신되는 순서가 달라지는 것은 알고있습니다.

제가 궁금한 내용은 근데 왜 그것때문에 오답정답이 갈리는지입니다.


예를들어 , k - i - j인 경우 

d[1][1] = min(d[1][1], d[1][1] + d[1][1])

d[1][2] = min(d[1][2], d[1][1] + d[1][2])

d[1][3] = min(d[1][3], d[1][1] + d[1][3])

...

d[1][1] = min(d[1][1], d[1][2] + d[2][1])

d[1][2] = min(d[1][2], d[1][2] + d[2][2])

d[1][3] = min(d[1][3], d[1][2] + d[2][3])

... 

이런 순으로 갱신되고


i - j - k 인 경우

d[1][1] = min(d[1][1], d[1][1] + d[1][1])

d[1][1] = min(d[1][1], d[1][2] + d[2][1])

d[1][1] = min(d[1][1], d[1][3] + d[3][1])

...

d[1][2] = min(d[1][2], d[1][1] + d[1][2])

d[1][2] = min(d[1][2], d[1][2] + d[2][2])

d[1][2] = min(d[1][2], d[1][3] + d[3][2])

...

이런 순으로 갱신이 될텐데 순서만 다를 뿐 i 에서 j로 가는 경로 중 k를 거쳐서 간다는 알고리즘 자체는 동일한 것 아닌가요 ??

wonkyum256   3년 전

플로이드-와샬 알고리즘을 살펴보면

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년 전

갱신이 모두 되지않은채로 해서그렇군요..

감사합니다

bliss08   1년 전

좋은 글 감사드립니다

댓글을 작성하려면 로그인해야 합니다.