플로이드 알고리즘

Question

플로이드 알고리즘을 공부하는데 몇가지 이해가 안되는 점이 있습니다. D의 k승은 k개의 정점을 지나는 최단 경로 길이의 행렬이고, 모든 정점을 지날 수 있는 최단 경로의 길이는  입니다. 즉, D에 주어진 행렬의 크기(길이)만큼 제곱을 해줘야 모든 경우의 수의 최단 경로를 알 수 있다는 것 입니다. 그런데 강의에서 제곱이 아닌 재귀관계식의 형태로 본것이 첫번째로 이해가 잘 되지 않고, 두번째는 제 생각에는 형태로 다른 정점  을 지나면 새로운 경로가 있는 경우가 되야 할것 같은데, 위와 같은 형태로  에서 k가 마치 함수의 매개변수 인것처럼 보이고 승수가 행렬의 인덱스처럼 사용되는 점이 이해가 되지 않습니다. 세번째는 재귀 관계식 를 이용해서  을 구해야 최단 경로의 길이를 구할 수 있는데,  로 n번의 연산과정이 있어야 함에도 단 한번의 플로이드 함수를 돌린 리턴값이  가 될 수 있는 이유를 모르겠습니다... 제가 봤을때는 한번 플로이드 함수가 돌리면 하나의 정점을 지난 최단 경로가 나와야 할것 같은데.... 이 세가지가 플로이드 알고리즘에서 이해가 되지 않는 부분입니다! 답변 해주시면 감사합니다!

joonion · Answer

네. 정확하게 이해하신 것 같습니다.

joonion · Answer

1. D^k는 수학에서의 행렬 거듭제곱과는 무관한 표기법입니다. W가 인접행렬이고, W=D^0으로 정의할 수 있으며, D^k는 플로이드 알고리즘에서 k번째 루프를 실행한 시점의 인접행렬로 이해해야 합니다. 2. 위 1번에서 처럼, k가 현재 계산된 경로 길이라고 생각하면 마치 매개변수처럼 사용되는 것은 이해가 가능할 것입니다. 3. 위 1번/2번의 오해를 교정해서 재귀식의 의미를 잘 곱씹어서 생각해 보면 D^n까지 진행하면 모든 쌍의 최단 경로 길이가 계산된 인접행렬을 얻는다는 것을 이해할 수 있습니다.