algorithm - Why no relaxing of all edges in the first iteration of Bellman Ford Algorithm?

Question

Please refer to the following page for Bellman ford algorithm (it shows an e.g). http://compprog.wordpress.com/2007/11/29/one-source-shortest-path-the-bellman-ford-algorithm

I still don’t get it. In the first loop iteration of the outer loop, let’s say by the example, u first modify edge 1->2 and edge 1->4, what’s the problem in relaxing the edge 2->3, 2->5, 4->3, 4->5,in the same step, since we have d[2] and d[4].

Answer 1

如果您使用稍微不同的 Bellman-Ford 版本，这个问题就会神奇地消失：

set toRelax = {initial_vertex}
while toRelax is not empty:
    u = remove a vertex from toRelax
    for each neighbour v of u:
       if we can relax u-v:
          relax u-v
          add v to toRelax

注意每个“步骤”现在如何涉及单个顶点！是否在“同一步骤”中完成的事情只是您使用的特定实现的产物，最终并不会真正改变算法。