Bellman-Ford 算法的最外层循环可以提前终止的吧？
来源：9-5 负权边和Bellman-Ford算法
磊磊要酷酷滴
2019-06-13
- 如果最外层的某次循环，distTo 和 from 都没有更新，那么下一次循环也不会再更新了，这时就可以提前退出最外层循环了；
- 这是我手画跟踪算法发现的问题，当然我是没能力在理论上证明啦；
- 想请教一下bobo老师对这个问题的看法；
写回答
1回答
-
赞！你是对的，没有问题的：）
因为如果在一次遍历中，没有任何一个边需要松弛的话，后续的遍历，也一定不会再可能松弛了。松弛的过程是根据from和distTo中的值作出判断，修改的也是from和distTo的值。如果在某一轮没有更改，后面的判断一定不会变了：）
所以可以在每轮循环中，设计一个变量，记录这一轮是否有松弛操作。如果没有，就可以退出循环了：）
再次赞主动用纸笔跟踪 + 自己独立思考！相信你对这个算法的认识比大多数同学更加深刻：）
继续加油！：）
00
相似问题