Bellman-Ford algorithm
Bellman-Ford algorithm适用于在含有负权值的图上求最短路径，是动态规划的一个应用，所以你需要阅读之前的一篇介绍动态规划的博文Dynamic Programming，抱歉，期末复习中，没有空闲翻译成中文。
Pseudocode of Bellman-Ford Algorithm
d[s] <- 0
for each v ∈ V-{s}
do d[v] <- ∞
for i <- 1 to |V|-1
do for each edge (u,v)∈E
do if d[v] > d[u] + w(u,v)
then d[v] <- d[u] = w(u,v) //relaxation step
for each edge(u,v)∈E
do if d[v]>d[u]+w(w,v)
then report that a negative-weight cycle exists
At the end, d[v] = δ(s,v), if no negative-weight cycles.
Time = O(VE)
一个实例
