7K12 blog

猫でも分かるアルゴリズム解説

AOJ GRL_1_C All Pairs Shortest Path

f:id:tkr987:20200716211812p:plain

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4675382

  • 全点対間最短経路はワーシャルフロイド法を使うと O(V^3)
  •  O(V^3)なので隣接行列に対して解が得られる
  • ワーシャルフロイド法では存在しない辺の値をinfにして渡す必要がある

f:id:tkr987:20200716220746p:plain
ワーシャルフロイド法は単純な三重ループで全点対間最短経路を見つける。例えばk=1のとき、 v_0から v_iへの道で v_1からのショートカットを使うべきかどうか判定する。このとき、 v_0から v_2までの経路は全探索したことになるので、 v_2までの最小値が確定する。k=2のとき、 v_2からのショートカットを使うべきかどうか判定し、 v_3までの最短経路が確定する。以下、再帰的に処理が実行されていき順次最短経路が確定し、最終的に全点対間最短経路が求まる。実装方法は螺旋本p336に載っている。