ワーシャル–フロイド法
ワーシャル–フロイド法の概略は以下の通りである:
入力: (有向または無向)グラフ G = ( V , E ) {\displaystyle G=(V,E)} E {\displaystyle E} の各辺の長さ
出力:頂点 i {\displaystyle i} と頂点 j {\displaystyle j} を結ぶ最短経路を全ての i , j ∈ V {\displaystyle i,j\in V} に対して出力
計算量: O ( V 3 ) {\displaystyle O(V^{3})}