Bellman-Ford法
Abstract
Bellman-Ford法は, 非負の辺重み$ wが与えられたネットワーク$ \mathcal{N} = \left((V, E), w \right)に対する単一始点最短経路問題を解くためのアルゴリズム. $ O(|V||E|)time. Explanation
TODO 書く.
Implementation
グラフ構築
Input
グラフの頂点数 N
グラフの各有向辺の始点 init, 終点 end, 重み weight
無向グラフにも対応可能.
Output
グラフの隣接リスト E
Time complexity
$ O(|E|)time.
最短距離の計算
Input
始点 s
Output
以下のいずれか.
負閉路が見つかった場合は None.
それ以外は s から各頂点への最短距離が入ったリスト dist
dist[t]: 頂点 s から頂点 t への最短距離
Time complexity
$ O(|V||E|)time.
最短経路の構成
Input
終点 t
Output
s から t への最短経路からなるリスト P
Time complexity
$ O(|V|)time.
code:python
class BellmanFord:
def __init__(self, N):
self.E = [[] for _ in range(N)]
def add_edge(self, init, end, weight, undirected=False):
self.Einit.append((end, weight)) if undirected: self.Eend.append((init, weight)) def distance(self, s):
INF = float('inf')
self.dist = INF * self.N # the distance of each vertex from s self.prev = -1 * self.N # the previous vertex of each vertex on a shortest path from s for _ in range(self.N):
updated = False
for v in range(self.N):
if d == INF: continue
temp = d + c
self.distu = temp; self.prevu = v updated = True
if not updated: break # the minimum costs are already stored in dist
else: return None # the above loop is not broken if and only if there exists a negative cycle
return self.dist
def shortest_path(self, t):
P = []
prev = self.prev
while True:
P.append(t)
if t == -1: break
Verification
References