ワーシャル–フロイド法
p i , j ′ = p i , j {\displaystyle p'_{i,j}=p_{i,j}} : そうでない場合。
よって K = 1 , . . . , k {\displaystyle K={1,...,k}} に対する最短経路 p i , j {\displaystyle p_{i,j}} が全ての i , j {\displaystyle i,j} に対して分かっていれば、 K ′ = 1 , . . . , k + 1 {\displaystyle K'={1,...,k+1}} に対する最短経路 p i , j ′ {\displaystyle p'_{i,j}} が全ての i , j {\displaystyle i,j} に対して求まる。
ワーシャル–フロイド法は以上の考察に基づいたアルゴリズムで、 K {\displaystyle K} を空集合に初期化後、 K {\displaystyle K} に頂点 1 , 2 , . . . , n {\displaystyle 1,2,...,n} を付け加えていくことで G = ( V , E ) {\displaystyle G=(V,E)} 上の最短経路を全ての i , j {\displaystyle i,j} に対して求める。