使用Bellman-Ford算法:遍历每条边的正确方式是什么？

Question

我正在做一个作业题，我需要从顶点z开始运行bellman-ford算法，它要求我“在每一次遍历中，以与图中相同的顺序放松边，并在每次遍历后显示d和pi值。”据我所知，我认为这个算法像BFS一样遍历图形，这从他们想要我使用的图形中是有意义的，所以我看不出相同的路径是如何工作的。如果有人能通过指出如何开始来给我指出正确的方向，那将是非常有用的。问题，以及问题所指的数字：

​

​

​

Answer 1

我会试着指出你的错误。

我以为这个算法像

一样遍历图形

这不是真的。这个算法反复迭代图形的所有边，并“松弛”它们，直到它达到稳定状态(当不能再松弛时)。

您附加的示例有点令人困惑，并且类似于BFS执行。这是因为在每次迭代中，它们只加粗了影响节点值的边(松弛的边)。

所以，为了回答你的问题，选择边缘的任何顺序，并开始所谓的“放松”它们。对于每条边，将其指向节点d值设置为到目前为止距Z的最短距离，并将其pi设置为其前置节点。重复此操作，直到所有值都稳定为止。

希望这回答了你的问题。

Answer 2

正如Ido.Co所说，在Bellman Ford中没有特定的扫描/迭代顺序。但是据说扫描广度优先的方式，执行起来更快。