ループの添字順序を間違えた Floyd-Warshall アルゴリズムを３回繰り返すと正しい結果が得られる - Qiita

Floyd-Warshall アルゴリズム は重み付き有向グラフのすべての頂点対に対して最短路距離を求める代表的なアルゴリズムです．グラフの頂点を $V = \{1, ..., n\}$ とし，$n \times n$ 配列 $d$ の $(i, j)$ 成分をグラフの $i, j$ 間の枝長 (枝がなければ $\infty$，$i = j$ はゼロ) で初期化してから以下の３重ループを実行すると，すべての頂点 $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-