Floyd-warshell Algorithm : 동적계획법의 일종 (수학과 컴퓨터 과학, 그리고 경제학에서 동적 계획법(動的計劃法, dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.) - 가중치 방향 그래프 G=(V,E), V = {1,2,... n} - 모든 노드 쌍들간의 최단경로의 길이를 구함 - d^k[i,j[ : 중간에 노드집합 {1,2...k}에 속한 노드들만 거쳐서 노드 i에서 j까지 가는 최단경로의 길이 ㄴ 노드 i에서 j까지 가는 최단경로는 두 가지 경우가 있다 (노드 k를 지나는 경우 , 지나지 않는 경우) i에서 j까지 경로가 k를 안 지나면 중간정점들이 모두 {1,2,...k}에 속한다. i에서 j까지의 경로가 k를 지나면 중간정점들이 모두 {1,2,... k-1}과 {1,2...k-1}에 속한다. 이 알고리즘은 처음에 모든 {\displaystyle (i,j)} 쌍에 대해서 {\displaystyle k=1} 일 때 {\displaystyle \mathrm {shortestPath} (i,j,k)} 를 계산하고, 다음으로 {\displaystyle k=2} 일 때를 계산하는 식으로 {\displaystyle k=N} 이 될 때까지 계속하면, 모든 {\displaystyle (i,j)} 쌍에 대해서 최단 경로를 찾게 된다. 기본적인 알고리즘의 의사코드는 다음과 같다: 1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity) 2 for each edge ( u , v ) 3 dist[ u ][ v ] ← w( u , v ) // 변 ( u , v )의 가중치 4 for...