그래프가 주어졌을 때, 모든 정점에서 대해서 다른 정점으로의 최단 경로를 구하는 것을 All Pair Shortest Path 이라고 한다. All Pair Shortest Path 를 구하는 알고리즘에는 플로이드-워셜 알고리즘이 있다. 플로이드 워셜 알고리즘은 일종의 동적 계획법(Dynamic Programming) 의 원리를 이용해서 모든 정점 쌍의 최단경로를 구한다. 알고리즘에 쓰이는 점화식을 나타내면 다음과 같다. dp[k][i][j] = min{dp[k - 1][i][j], dp[k - 1][i][k] + dp[k - 1][k][j]}; dp[k][i][j] 는 (1, 2, … , k) 에 속한 정점만을 경유하여 정점 i에서 정점 j로까지 도달할때 최단길이를 의미한다. 이 때 정점 k를 경유하는..