赞
踩
贝尔曼-福特(Bellman-Ford)算法是一种在图中求解最短路径问题的算法。最短路径问题就是在加权图指定了起点和终点的前提下,寻找从起点到终点的路径中权重总和最小的那条路径。
这里我们设A为起点、G为终点,来讲解贝尔曼-福特算法。首先设置各个顶点的初始权重:起点为0,其他顶点为无穷大(∞)。这个权重表示的是从A到该顶点的最短路径的暂定距离。随着计算往下进行,这个值会变得越来越小,最终收敛到正确的数值。
从所有的边中选出一条边,此处选择了连接A-B的边。然后,分别计算这条边从一端到另一端的权重,计算方法是“顶点原本的权重+边的权重”。只要按顺序分别计算两个方向的权重即可,从哪一端开始都没有问题。此处我们选择按顶点权重从小到大的方向开始计算。
A的权重小于B,因此先计算从A到B的权重。A的权重是0,边A-B的权重是9,因此A到B的权重是0+9=9。如果计算结果小于顶点的值,就更新这个值。顶点B的权重是无穷大,比9大,所以把它更新为9。更新时需要记录计算的是从哪个顶点到该顶点的路径。
接下来计算从B到A的权重。B的权重为9,从B到A的权重便为9+9=18。与顶点A现在的值0进行比较,因为现在的值更小,所以不更新。
对所有的边都执行同样的操作。在执行顺序上没有特定要求,此处我们选择从靠近左侧的边开始计算。先选出一条边C。因为0+2=2小于正无穷,数值更新了,顶点C的权重变成了2。
更新完所有的边后,第1轮更新就结束了。接着,重复对所有边的更新操作,直到权重不能被更新为止。
第2轮更新也结束了。顶点B的权重从8变成了7,顶点E的权重从9变成了8。接着,再执行一次更新操作。
第3轮更新结束,所有顶点的权重都不再更新,操作到此为止。算法的搜索流程也就此结束,我们找到了从起点到其余各个顶点的最短路径。
根据搜索结果可知,从起点A到终点G的最短路径是A-C-D-F-G,权重为14。
notes:贝尔曼-福特算法的名称取自其创始人理查德·贝尔曼和莱斯特·福特的名字。贝尔曼也因为提出了该算法中的一个重要分类“动态规划”而被世人所熟知。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。