
No.
4-4
ベルマン
-
フォード法は、グラフの最短路問題を解くアルゴリズムです。最短路問題では、辺 に
コストの付いた「辺重み付きグラフ」が与えられ、「始点」と「終点」が指定されています。始点
から終点へ至る路のうち、間を通る辺のコストの総和が最も小さいものを求める問題です。
B E
C F
GD
1
9
39 5 7
6 3
22 6 4
A
は
A
G
とてベルマン
-
フォード法明
B
E
C
∞
F
∞
G
∞
D
∞
A 0
6 3
1
9
39 5 7
22 6 4
のコストの定は
0
のはに定
のコストは
A
のの定ののさ計算につての
さりにいに
01
02
はい
いの
いの
てい