看到好几个Bellman-Ford算法都是这样写的，我有个疑问

Question

for(int i = 1; i <= nodenum - 1; ++i)

for(int j = 1; j <= edgenum; ++j)

if(dis[edge[j].v] > dis[edge[j].u] + edge[j].cost) //松弛(顺序不能错）

{

dis[edge[j].v] = dis[edge[j].u] + edge[j].cost;

pre[edge[j].v] = edge[j].u;

}

在Bellman 算法里松弛操作只要对所有边进行就可以了吧，并不要按照一定的次序进行松弛操作。所以我把上面的代码改成

for( i = 1; i <= nodenum - 1; ++i)
for( j = edgenum; j >=1; --j)
{
if(dis[edge[j].v] > dis[edge[j].u] + edge[j].cost) //松弛（顺序一定不能反~）
{
dis[edge[j].v] = dis[edge[j].u] + edge[j].cost;
pre[edge[j].v] = edge[j].u;
}
}
运行结果一样。
但是这个代码里每次松弛操作后会立马修改dis[]，而《算法导论》中如图
图片说明
并不是立即修改dis[]的。
我不知道是不是我对Bellman-Ford理解错了还是立即修改dis[]不会对算法结果产生影响

Answer 1

http://baike.baidu.com/link?url=UO7Fnxb-jHNj3X7idE9srNHZHuOxDrBaTKiw2bB0FNmo1upbRYe9nw1DzJGdKWoM2kpMxCkuXkbn4XtRs08c0q