首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >我很难理解贝尔曼·福特的迭代

问我很难理解贝尔曼·福特的迭代
EN

Stack Overflow用户
提问于 2013-01-17 00:58:21
回答 1查看 612关注 0票数 3

向我解释Bellman Ford算法的方式是,它经历n-1 (n是节点的数量)迭代,在每次迭代中更新节点之间的距离。所有图形示例都显示了初始化为无穷大的节点,并且最接近源节点的节点在第一次迭代时被更新,但其余的节点保持为无穷大,直到迭代到达它们。

然而,查看算法的代码,例如提供的here,我发现很难理解为什么所有比迭代次数更远的节点都没有使用算法进行更新。例如,如果我在第二次迭代中,我有一个只能通过路径a-b-c-d到达的节点d,我读到的示例似乎表明d在第四次迭代之前不会更新。

但代码的主要松弛功能是:

代码语言:javascript
复制
def relax(node, neighbour, graph, d, p):
    # If the distance between the node and the neighbour is lower than the one I have now
    if d[neighbour] > d[node] + graph[node][neighbour]:
        # Record this lower distance
        d[neighbour]  = d[node] + graph[node][neighbour]
        p[neighbour] = node

基于给出权重和与前导节点的源的距离的信息进行更新。如果算法在每次迭代中遍历每个节点,那么什么可以阻止d在第一次迭代中被正确更新?例如,如果算法按a- b -c-d的顺序迭代节点,我不明白为什么算法不存储节点b的距离信息,移动到节点c,存储该节点的距离信息,最后在第一次迭代中获得足够的信息来计算最短路径。

我希望这是有意义的。

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2013-01-17 01:11:03

这是有可能发生的--但这并不能保证。您只能保证在第k次迭代时,您拥有的最短路径长度一直到k,而不是更早。

您看到的可视化只是为了解释算法的概念,而且使用事务内存模型可以更清晰、更简单地理解。

想象一下,如果距离为10的节点在第一次迭代中发生变化,那么使用可视化来理解算法是多么困难……

关于评论中的问题:

这是否意味着我可以有效地创建一个工具来跟踪每次迭代的更改数量,并且一旦计数器达到0,我就可以提前退出迭代?

是的,如果迭代k没有变化-迭代k+1也不能改变任何东西,一切都是最小的,k+2也是如此,...

票数 4
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/14363655

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档