4.4.2 - Bellman-Ford algorithm

$Dist^k[i]$ : 代表起點到 $i$ 的shortest path length，至多經過 $k$ 個邊。

$Dist^1$ 為Cost Matrix起點的那一列值，依序求出 $Dist^2,\ Dist^3...Dist^{n-1}$

$Dist^k[i]=\min\{Dist^{k-1}[i],\ \min \{Dist^{k-1}[u]+C[u, i]\}$

e.g.

Last updated 6 years ago

$Dist^k[i]$ : 代表起點到 $i$ 的shortest path length，至多經過 $k$ 個邊。

$Dist^1$ 為Cost Matrix起點的那一列值，依序求出 $Dist^2,\ Dist^3...Dist^{n-1}$

$Dist^k[i]=\min\{Dist^{k-1}[i],\ \min \{Dist^{k-1}[u]+C[u, i]\}$

e.g.