如何根据最小道路上的最大拱数停止Bellman-Ford算法
如何根据最小道路上的最大拱数停止Bellman-Ford算法
提问于 2020-07-03 22:37:32
设G= (V，E)是不含负圈的有向赋权图。如何修改福特bellman算法，使其在while循环的m+1次迭代后停止。M是最小路径中的最大弧数(根据权重而不是道路中拱门的数量确定的最小道路)
回答 2
Stack Overflow用户
发布于 2020-07-03 22:56:39
Bellman-Ford算法是一种计算从单个源顶点到加权有向图中所有其他顶点的最短路径的算法。除非你不关心一个确切的解决方案，否则你不能提前结束它。
Stack Overflow用户
发布于 2021-09-06 07:06:06
您可以简单地添加一个布尔标志来检查是否发生了松弛，即是否更新了任何距离。因为我们已经知道最短路径包含m条边，在前m次迭代之后，松弛不会发生，距离也不会改变。因此，根据定义的布尔标志，您可以提前终止循环。这将时间复杂度从O(V_E)提高到O(m_E)。
下面是实现- https://cp-algorithms.com/graph/bellman_ford.html#toc-tgt-3
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/62717616
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号