ワーシャル–フロイド法
i {\displaystyle i} から j {\displaystyle j} への最短経路を p i , j {\displaystyle p_{i,j}} とし、 u {\displaystyle u} と v {\displaystyle v} を p i , j {\displaystyle p_{i,j}} 上の頂点とすると、 u {\displaystyle u} から v {\displaystyle v} への最短経路(の一つ)は p i , j {\displaystyle p_{i,j}} を u {\displaystyle u} 、 v {\displaystyle v} 間に制限したものと一致する。 したがって p i , j {\displaystyle p_{i,j}} さえ知っていれば p u , v {\displaystyle p_{u,v}} を計算する必要もないし記憶する必要もない。 このことを利用すると、ワーシャル–フロイド法における計算量と記憶量を大幅に減らすことができる。
計算量が増えてしまうことを厭わなければ、さらに記憶量を減らすこともできる。 k {\displaystyle k} を一つ固定し、 K = 1 , . . . , k {\displaystyle K={1,...,k}} に対する最短経路 p i , j {\displaystyle p_{i,j}} が全ての i , j {\displaystyle i,j} に対して求まっているとする。