4.4.2 - Bellman-Ford algorithm

• 可有負邊存在

1. 演算法

$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.