～ ワーシャルフロイド法 ～ チートシート

目次

ワーシャルフロイド法とは
実装

もしかして：ダイクストラ法

はじめに

チートシートの扱いついてはここを読んでください

ワーシャルフロイド法とは

わかりやすいサイト

全ての頂点間に対し、別の頂点を経由するとコストが低くならないかを調べることで、全頂点間の最小移動コストを求めるアルゴリズム
全頂点が始点となる場合に有効
計算量が大きいので、始点が１つに定まっている場合はダイクストラ法を使う
コストが負の経路があっても使うことができる
コストが負の閉路に注意

実装

問題（Atcoderだと簡単な問題がなかったので、AIZU ONLINE JUDGEより）

Floyd–Warshall_algorithm.py

BIG = 999999999999999
N,M = map(int,input().split()) #頂点の数、辺の数
mat = [[BIG] * (N+1) for i in range(N+1)] #最短距離の候補を格納する配列（mat[A][B]：AからBの最短経路）
for i in range(N+1):
  mat[i][i] = 0

for i in range(M):
  A,B,C = map(int,input().split()) #辺の始点、辺の終点、移動に必要なコスト
  mat[A][B] = C

def warshall_floyd():
  flag = 1 #収束判定用の変数
  for i in range(N):
    for j in range(N):
      for k in range(N):
  #for i in range(1,N+1): #頂点の番号が1,2,3...と振られている場合（Atcoder用）
    #for j in range(1,N+1): #頂点の番号が1,2,3...と振られている場合（Atcoder用）
      #for k in range(1,N+1): #頂点の番号が1,2,3...と振られている場合（Atcoder用）
        N,M = map(int,input().split()) #頂点の数、辺の数
mat = [[0] * (N+1) for i in range(N+1)] #最短距離の候補を格納する配列（mat[A][B]：AからBの最短経路）
for i in range(N+1):
  mat[i][i] = 0

for i in range(M):
  A,B,C = map(int,input().split()) #辺の始点、辺の終点、移動に必要なコスト
  mat[A][B] = C

def warshall_floyd(K):
  flag = 1 #収束判定用の変数
  for i in range(1,N+1): #頂点の番号が1,2,3...と振られている場合（Atcoder用）
    for j in range(1,N+1): #頂点の番号が1,2,3...と振られている場合（Atcoder用）
      for k in range(1,K): #頂点の番号が1,2,3...と振られている場合（Atcoder用）
        #BIG=0とする場合、ループ(i=j)に注意しながらmat[i][j]=0の時の処理を追加する
        #if mat[i][j] == 0 and mat[i][k] != 0 and mat[k][j] != 0 and i != j:
          #mat[i][j] = mat[i][k] + mat[k][j]
          #flag = 0
        if mat[i][j] > mat[i][k] + mat[k][j] and mat[i][k] != 0 and mat[k][j] != 0:
          mat[i][j] = mat[i][k] + mat[k][j]
          flag = 0
          if mat[i][i] < 0: #コストが負の閉路がある場合の処理
            print("NEGATIVE CYCLE")
            exit()
  return flag

ans = 0
for K in range(1,N+1):
  while True:
    check = warshall_floyd(K+1)
    if check == 1:
      break
  #print(K,mat)
  for m in range(1,N+1):
    for n in range(1,N+1):
      ans += mat[n][m]
print(ans)
        if mat[i][j] > mat[i][k] + mat[k][j] and mat[i][k] != BIG and mat[k][j] != BIG:
          mat[i][j] = mat[i][k] + mat[k][j]
          flag = 0
          if mat[i][i] < 0: #コストが負の閉路がある場合の処理
            print("NEGATIVE CYCLE")
            exit()
  return flag

while True:
  check = warshall_floyd()
  if check == 1:
    break

ans = [[0] * (N) for i in range(N)] #答えを格納するための配列
for i in range(N):
  for j in range(N):
    ans[i][j] = mat[i][j]
    #ans[i][j] = mat[i+1][j+1] #頂点の番号が1,2,3...と振られている場合（Atcoder用）
    if ans[i][j] == BIG:
      ans[i][j] = "INF"
[print(*ans[i]) for i in range(len(ans))]

Atcoderと異なりインデックスが0始まりなので注意（Pythonと同じだからこっちの方がありがたいけど）
コストが負の閉路（始点と終点が同じ頂点であるループ）があると、そこを永遠に周回することでコスト-∞を達成してしまうので注意
ライブラリshortest_path()を使うという手もあるけど、Atcoderだとなんかめんどくさいらしい