アルゴリズム/ワーシャルフロイド法(WF) - projecthikky @ ウィキ

概要

与えられたグラフにおいて、全ての２点間の最短距離を求めるアルゴリズム。（全点対間最短距離問題）
計算量は頂点数をNとすると、O(N^3)。競技プログラミングにおいてはN<=300程度までなら適用できるか。
辺の重みが負であってもよい、負の閉路があることを検出することも出来る。
実装するだけなら三重ループを書くだけで実装できるので比較的楽で覚えやすいアルゴリズム。

解説ブログなど

ワーシャルフロイド法とその例題 - ゆらのふなびと

問題

AOJ Shortest Path - All Pairs Shortest Path
ABC051 D - Candidates of No Shortest Paths