floyd-warshall algorithm

Floyd-Warshall 알고리즘은 all-to-all 알고리즘이다. 이전의 djikstra 알고리즘 같은 경우 one-to-one인 알고리즘이다.

Notation

d_k[i,j] : i 에서 j까지 {1,2,...,k}까지의 노드들만 지나서 가는 경로

d_0[i,j] = 0 if w[i,j] doesn't exist

d_n[i,j] = 최단경로 ( 중간에 어떤 노드를 지나도 상관 없으므로)

d_k[i,j] = min(d_k-1[i,j],d_k-1[i,k]+d_k-1[k,j])