【Python】ベルマン・フォード法【アルゴリズム】

ベルマン・フォード法について
1. 概要
2. 流れ
コード
参考

ベルマン・フォード法について

概要

最短経路問題を解くために使われる
頂点を結んだ辺の重みを更新しながら解いていく
辺の値が負の値でも使える

流れ

辺を選ぶ
辺の両端にあるコストを更新する
全ての辺に対して作業ができたら、最初からもう一度行う
全ての頂点のコストが更新されなくなったら終了する

コード

def bellman_ford(edges, num_v):
  dist = [float('inf') for i in range(num_v)]  #無限大(float('inf'))をnum_vの数だけ要素に持つリストを作る
  dist[0]=0 #スタート地点のコストを0にする
  changed = True                               #コストが更新されたことを示すフラグ
  while changed:                               #コストが更新される限り繰り返す
    changed = False 
    for edge in edges:
      if dist[edge[1]] > dist[edge[0]] + edge[2]:   #終点のコストが起点のコスト＋辺のコストより大きい場合
          dist[edge[1]] = dist[edge[0]] + edge[2]   #終点のコストを起点のコスト＋辺のコストに更新
          changed = True                            #頂点のコストが更新されたのでTrutにしてフラグを立てる
  return dist 

edges = [[0,1,4],[0,2,3],[1,2,1],[1,3,1],[1,4,5],[2,5,2],[4,6,2],[5,4,1],[5,6,4]]
#辺と頂点のリスト　[[起点、終点、コスト],[起点、終点、コスト],[起点、終点、コスト]]の順に並んでいる

print(bellman_ford(edges,7))    
#[0, 4, 3, 5, 6, 5, 8]

def bellman_ford(edges, num_v):

dist = [float('inf') for i in range(num_v)] #無限大(float('inf'))をnum_vの数だけ要素に持つリストを作る

dist[0]=0 #スタート地点のコストを0にする

changed = True #コストが更新されたことを示すフラグ

while changed: #コストが更新される限り繰り返す

changed = False

for edge in edges:

if dist[edge[1]] > dist[edge[0]] + edge[2]: #終点のコストが起点のコスト＋辺のコストより大きい場合

dist[edge[1]] = dist[edge[0]] + edge[2] #終点のコストを起点のコスト＋辺のコストに更新

changed = True #頂点のコストが更新されたのでTrutにしてフラグを立てる

return dist

edges = [[0,1,4],[0,2,3],[1,2,1],[1,3,1],[1,4,5],[2,5,2],[4,6,2],[5,4,1],[5,6,4]]

#辺と頂点のリスト　[[起点、終点、コスト],[起点、終点、コスト],[起点、終点、コスト]]の順に並んでいる

print(bellman_ford(edges,7))

#[0, 4, 3, 5, 6, 5, 8]

参考

こちらの書籍を用いて学習しています。

問題が書籍の中にあります。図を使って各頂点と各辺のコストが示されているので、書籍を手元に準備すると理解しやすくなると思います。