本文主要是介绍Bellman-Ford算法寻找最短路径可用于计算机网络,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
从s开始看指向别的节点的边
s有两条边,一条指向E,另外一条指向A,更新表中s与A和E的距离
然后从A开始看指向别的节点的边,指向C的边,加上s到A的距离就是s到C的距离并更新表中C的数据
然后从B开始,但是我们发现暂时没有到B的边,所以先跳过B
从C开始,只有一条指向B的边,加上从s到C的距离就是s到B的距离并更新表中B的数据
从D开始,我们暂时没有发现到D的路径,于是跳过D
从E开始,只有一条指向D的路径,加上从s到E的距离就是s到D的距离并更新表中D的数据
此时我们完成了第一次迭代,我们需要完成所有节点数-1次迭代即5次迭代
让我们开始第二次迭代
第二次迭代中,再次从s开始观察是否有指向别的节点的边可以更改最短距离
发现s A B C都未能改变最短距离故而不需要更新表中值
到D节点的时候,我们发现通往A和C的路径减少了
从s到D距离9加上通往A的距离-4更新s到A最短距离5
从s到D距离9加上通往C的距离-1更新s到A最短距离8
再到E节点,未能改变最短距离故而不需要更新表中值
完成第二次迭代,开始第三次迭代
开始第四次迭代
注意此时并不需要第5次迭代,因为n-1是迭代最多需要次数,所以当一次迭代中没有任何值变化,就可以提前停止
这篇关于Bellman-Ford算法寻找最短路径可用于计算机网络的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!