Floyd-Warshall アルゴリズム は重み付き有向グラフのすべての頂点対に対して最短路距離を求める代表的なアルゴリズムです.グラフの頂点を $V = \{1, ..., n\}$ とし,$n \times n$ 配列 $d$ の $(i, j)$ 成分をグラフの $i, j$ 間の枝長 (枝がなければ $\infty$,$i = j$ はゼロ) で初期化してから以下の3重ループを実行すると,すべての頂点 $i$, $j$ についてそれらの間の最短路長が $d[i,j]$ に入ります(ただしグラフは負閉路をもたないとします). # Floyd-Warshall アルゴリズム for k = 1, ..., n: for i = 1, ..., n: for j = 1, ..., n: d[i,j] = min(d[i,j], d[i,k] + d[k,j]) ところで,Floyd-