http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4675382
- 全点対間最短経路はワーシャルフロイド法を使うと
なので隣接行列に対して解が得られる
- ワーシャルフロイド法では存在しない辺の値をinfにして渡す必要がある
ワーシャルフロイド法は単純な三重ループで全点対間最短経路を見つける。例えばk=1のとき、から
への道で
からのショートカットを使うべきかどうか判定する。このとき、
から
までの経路は全探索したことになるので、
までの最小値が確定する。k=2のとき、
からのショートカットを使うべきかどうか判定し、
までの最短経路が確定する。以下、再帰的に処理が実行されていき順次最短経路が確定し、最終的に全点対間最短経路が求まる。実装方法は螺旋本p336に載っている。
