有向グラフ上の2点間の最短距離を求めるアルゴリズム Bellman–Ford 法を python で書いてみる

有向グラフとは

有向グラフ(directed graph)とは, 頂点(vertex)と辺(edge)からなり, 辺は  (v_1, v_2, c) の形式を持ち, 頂点 v_1 から頂点 v_2 へはコスト c で移動できることを表しています. 辺に対して逆向きの進路があるとは限らず, あったとしても同じコストとは限りません.
今回はグラフの情報と始点が与えられたとき, 各頂点への最短距離をベルマン=フォード法と呼ばれるアルゴリズムで求めていきます.
また, 有向グラフ上の2点間の最短距離を求めるアルゴリズムにはダイクストラ(Dijkstra)法と呼ばれるものもありますが, ベルマン=フォード法の強みは辺の重みは負でもよいことが挙げられます.
一方, 負の重みを持つ辺があるときに考えなくてはならないのは負閉路の検出です. 閉路を一周するごとに距離をマイナスにすることができるものが存在する場合, その閉路を何度も通ることで最短距離をいくらでも縮めることができてしまい, 最短経路が定まりません. ですので負閉路が存在(かつ始点から到達)する場合には最短距離の代わりに警告を返します.

Bellman–Ford 法のアルゴリズム

まず, 負閉路が存在しない仮定のもと, 始点から出発して隣接する頂点までの距離を辺の情報から求めます.
次に, 到達済みの頂点から出発して隣接する頂点までの距離を辺の情報から求めます. このとき, その頂点にすでに到達していた場合にはすでに求められていた距離と比較して, より小さい場合には距離を新たな(小さな)ものに書き換えていきます. このことを距離を緩和(relaxing)するといいます.
漸次このステップを \text{"頂点の個数"}-1 回繰り返せば, これで最短距離を表す配列が完成したことになります. なぜなら, それ以上のステップで到達した経路は負閉路または非負閉路を通っていることになり, 前者は負閉路が存在しないという仮定から排除され, 後者の場合は距離の緩和が起こらないからです.
最後に, 負閉路の存在をチェックします. 負閉路が存在した場合, 負閉路のパスの長さは頂点の個数以下なので, ステップを \text{"頂点の個数"}-1 回繰り返した後に, もう一度ステップを繰り返すと負閉路を一周して緩和が発生してしまいます. ですので緩和が発生した場合には警告を返し, 発生しなかった場合には先ほど求めた配列を返します.
コードは次のようになります:

def BellmanFord(edges,num_v,source):
  #グラフの初期化
  inf=float("inf")
  dist=[inf for i in range(num_v)]
  dist[source-1]=0
  
  #辺の緩和
  for i in range(num_v):
    for edge in edges:
      if edge[0] != inf and dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
        dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
        if i==num_v-1: return -1
  
  return dist

上のコードでは辺の緩和を頂点の個数回行い, 最終回に緩和があった場合には負閉路を含む緩和が発生したものとみなして-1を返し, そうでない場合は配列 dist を返します.