我正在做一个作业问题，我需要从顶点 z 开始运行 bellman-ford 算法。它要我“在每次通过时，按照与图中相同的顺序放松边缘，并在每次通过后显示 d 和 pi 值。” 据我了解，我认为这个算法像 BFS 一样遍历图形，这从他们希望我使用的数字来看是有意义的，所以我看不出相同的路径是如何工作的。如果有人可以通过指出如何开始来为我指明正确的方向，那将非常有用。问题和问题所指的数字：
问问题
3170 次
2 回答
2
我会尽力指出你的错误。
我认为这个算法像 BFS 一样遍历图形
这不是真的。该算法反复迭代图的所有边，并“放松”它们，直到它达到稳定状态（当不能再进行放松时）
您附加的示例有点混乱，类似于 BFS 执行。这是因为在每次迭代中，它们仅将影响节点值的边加粗（松弛的边）。
因此，要回答您的问题，请为边缘选择任意顺序，然后开始所谓的“放松”它们。对于每条边，将其指向节点 d 值设置为距 Z 的最短距离，并将其 pi 设置为其前驱节点。重复此操作，直到所有值都稳定为止。
希望这能回答你的问题。
于 2011-11-27T10:03:54.010 回答
0
正如 Ido.Co 所说，在 Bellman Ford 中，没有特定的扫描/迭代顺序。但据说扫描广度优先方式，执行速度更快。
于 2017-01-22T13:08:51.447 回答