No Caffeine, No Life

プログラミング(主にPython)

AOJ GRL_1_C:全点対間最短経路 ワーシャルフロイド法 (Warshall-Floyd's Algorithm)

全点対間最短経路問題 (APSP: All Pairs Shortest Path)を解くアルゴリズムのひとつにワーシャルフロイド法がある。

特徴:

  • Gに負の閉路がない限り、Gに負の重みをもつ辺が存在しても適用可。
  • Gに負の閉路があるかどうかの判定に使える。すなわち、ある頂点vから頂点v(それ自身)への最短距離が負になれば、Gに負の閉路が存在すると判断できる。

問題:

全点対間最短経路 | グラフ | Aizu Online Judge

ワーシャルフロイドはO(|V^{3}|)のアルゴリズム