Pseudo Code
Coddyの「ベルマン–フォード法 - グラフアルゴリズム」コースのレッスン 4/9。
bellmanFord(n, edges, source):
dist = [INF, INF, ...]; dist[source] = 0
repeat (n - 1) times:
for each edge (u -> v, weight w):
if dist[u] != INF and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
残っているすべての INF を -1 に置き換える
return dist
// 負の閉路: n-1 回のパスの後、依然として辺が緩和（relax）される場合、
// 負の閉路が存在します。- ガード
dist[u] != INFは、到達不可能な頂点からパスが構築されるのを防ぎます。 - 辺リスト全体を緩和することが 1 回のパスです。ベルマン–フォード法は、そのパスを
n - 1回繰り返すだけです。
自分で試してみよう
このレッスンにはコードチャレンジは含まれていません。
腕試しこのレッスンには短いクイズがあります。レッスンを始めて解答し、進捗を記録しましょう。
ベルマン–フォード法 - グラフアルゴリズムのすべてのレッスン
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity