Floyd-Warshall
全点対最短経路アルゴリズム。すべての頂点の組について最短経路を一度に求める。ロバート・フロイドとスティーブン・ウォーシャルによる1962年の定式化。
動的計画法による美しい定式化で、中継点 k ごとに dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) を更新する。三重ループで書けて、実装は8行ほど。計算量は O(V³) なので大きなグラフには向かないが、200頂点未満なら十分に実用的だ。
小規模ネットワークのルーティング表、推移閉包、ソーシャルグラフ上の「二人をつなぐ最短の知り合い経路」などに使われる。負の辺は扱えるが、負閉路は扱えない。疎なグラフではジョンソン法（V·E·logV）のほうが有利である。