제목의 대의: N변을 지나는 최단로를 구한다.좋은 문제는 플로이드와 그림의 인접 행렬의 곱셈을 더욱 깊이 이해했다.이 문제는 두 점 사이의 N 라인을 통과하는 경로수와 비슷하지만 그림의 인접 매트릭스 A 메모리 그림을 사용하면 2분 매트릭스 빠른 멱 A^N이 구하는 것임을 알 수 있다.경로수를 매트릭스 곱셈으로 구할 수 있는 이유는 그의 상태 방정식이 매트릭스 곱셈과 같기 때문이다. dp[i][j][p]를 설정하면 i가 j점에서 p줄의 가장자리를 통과하는 경로수를 나타낸다. 그러면 dp[i][j][p]=sigma(dp[i][k][p-1]*dp[k][j]]]를 설정하면 A=B*C(dp[p]를 A로 보고 dp[p-1]를 B로 본다.그러나 분명히 최단로의 방정식은 그렇지 않다.Floyd의 방정식에 따르면 이것은 dp[i][j]=min(dp[i][j], dp[i][k]+dp[k][j])이어야 한다.그러면 이런 방정식을 위의 방법과 유사하게 구할 수 있습니까?답은 긍정적이니 곱셈만 고치면 된다.분명히 행렬 연산이 결합율에 부합되기만 하면, 그것은 이분 행렬의 빠른 멱으로 할 수 있다.위의 플로이드 방정식이 결합률에 부합한다는 증명에 대해 유화정의 논문인 은 증명이 있지만 그의 앞의 나는 이해하지 못했다...그러면 우리가 행렬의 곱셈을 C[i][j]=min(C[i][j], A[i][k]+B[k][j])로 다시 정의하면 문제가 쉽게 풀린다.만약에 우리가 그림의 인접 행렬이 VE라면 위의 정의에 따르면 VE*VE는 두 개의 변을 통과하는 데 필요한 가장 짧은 경로에 도달하는 것이 분명하다.그리고 같은 VE ^ N은 N라인을 통과하는 데 필요한 가장 짧은 경로입니다.왜 이 유사한Floyd식이 구한 것은 변수의 가장 짧은 거리를 확정한 것입니까?이 업데이트는 플로이드와 달리 새로운 행렬로 업데이트되기 때문에 플로이드처럼 자신을 업데이트하는 것이 아니다.따라서 업데이트가 되면 자신이 새로 업데이트한 값이 나타나지 않고 계속 업데이트됩니다.
