ワーシャルフロイド法

蟻本で出てきた。ダイクストラとかはまだちょっと飲み込み切れてないけどこれは割と簡単だと思った。
ノードiからノードjに行くまでに、ノードkを経由するかしないかの距離短い方を全ノード間について選んで、最短経路を求める感じ。
i->jまでが距離xなら、d[i][j] = xみたいにして引数に渡すと全ノード間のコストが戻ってくる。

#あるノードからあるノードまで行く場合のコストを全部求めて最小を選んでいる
def warshall_floyd(d):
  #d[i][j]はノードiからノードjへの辺のコスト。存在しないならINF、i=jは０とする
  for k in range(len(d)):
    for j in range(len(d)):
      for i in range(len(d)):
        d[i][j] = min(d[i][j], d[i][k] + d[k][j]) #kを通らない場合とｋ経由の場合のコストが小さいほう
        
  return d