zpapl   2년 전

플로이드 알고리즘에서 모든 정점의 쌍에 대해서 최단 경로를 구해줄 때

for(k = 0 to N)

for(i = 0 to N)

  for(j = 0 to N)

   dist[i][j] = dist[i][k] + dist[k][j]

이렇게 보통 쓰는데 왜 순서를 바꾸면 알고리즘이 제대로 작동하지 않죠..??

위의 코드는 조건을 빼고 큰 흐름만 바라본 것입니다.

ploffer11   2년 전

k는 경유하는 정점이기 때문에 i와 j만 위치를 바꾼다면 몰라도 k를 바꾸면 알고리즘 의도와 맞지 않을 것 같습니다.

zpapl   2년 전

만약

for(i = 0 to N)

for(j = 0 to N)

  for(k = 0 to N)

이렇게 있어도

k를 경유하는 i->k->j의 의미는 동일 하지 않나요?

ploffer11   2년 전

k를 경유하는 모든 노드를 갱신시켜주고 그다음에 새로운 경유노드로 갱신시켜줘야 하는데 경유노드가 저렇게 계속 바뀌면 의미가 없을 것 같습니다.

플로이드 워셜 자체가 0번노드를 경유하는 최단 경로 업데이트 -> 이정보를 사용해 1번노드를 경유하는 최단 경로 업데이트... N-1번 노드를 경유하는... 까지 가는거니까요

jh05013   2년 전

플로이드 알고리즘의 원리는 "dp[i][j][k] = "i에서 j까지 가되, 중간에 경유하는 모든 정점의 번호가 k 이하인 최단거리"를 2차원 배열로 바꾼 것이고, dp[i][j][k] = min(dp[i][j][k-1], dp[i][k][k-1]+dp[k][j][k-1]입니다.

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