贝尔曼-福特算法是一种在图中求解最短路径的问题的算法。
最短路径问题就是加权图在指定了起点和终点的前提下，寻找从起点到终点的路径中权重总和最小的那条路径。
1
以上图示为例子来回顾算法实现步骤
设图1中A为起点，G为终点。
因为A为起点，则A的权重设置为0。
在最初并不知道要走多远才能到达其他顶点，因此先将起点以外的顶点，权重设置为无限大。如下，这个权重表示的是从A点到该点的最短距离。
A 0
B +∞
C +∞
D +∞
E +∞
F +∞
G +∞
随着计算的进行，这个距离的值会越来越小，最终收敛到正确的数值。
首先选出一条路径A-B
计算顶点B的权重为 0（顶点A的权重） + 9（A-B的路径权重） = 9，因为9小于顶点B默认的权重正无穷，所以顶点B的权重更新为9，且记录顶点B更新权重为9的路径为A-B.
接下来计算A的权重，9（顶点B当前的权重） + 9（B-A的路径权重）= 18，因为18大于顶点A原有的顶点权重0，所以顶点A的权重不更新。
A 0
B 9 A - B
C +∞
D +∞
E +∞
F +∞
G +∞
以上描述就是关于贝尔曼-福特算法的基本组成。
接下来按照上面的描述，一步一步计算每个顶点的权重。
继续...
选择一条路径A-C 得到结果顶点C的权重是2，记录顶点C的权重路径为A-C
计算A的权重 A = C + 2 = 2 + 2 = 4 > 0 所以A权重不更新。
A 0
B 9 A - B
C 2 A - C
D +∞
E +∞
F +∞
G +∞
选择一条路径C-B，计算C的权重为B + 6 = 9 + 6 = 15 > 2 ,因此C的权重不更新。
计算B的权重 = C + 6 = 8 < 9 ,更新B的权重为8 ，且记录B最短路径为A-C-B。
A 0
B 8 A - C - B
C 2 A - C
D +∞
E +∞
F +∞
G +∞
选择路径B - E
A 0
B 8 A - C - B
C 2 A - C
D +∞
E 9 A - C - B - E
F +∞
G +∞
选择路径B - D
A 0
B 8 A - C - B
C 2 A - C
D 11 A - C - B - D
E 9 A - C - B - E
F +∞
G +∞
选择路径C - D
A 0
B 8 A - C - B
C 2 A - C
D 4 A - C - D
E 9 A - C - B - E
F +∞
G +∞
选择路径C - F
A 0
B 8 A - C - B
C 2 A - C
D 4 A - C - D
E 9 A - C - B - E
F 11 A - C - F
G +∞
选择路径D - E ,不更新
A 0
B 8 A - C - B
C 2 A - C
D 4 A - C - D
E 9 A - C - B - E
F 11 A - C - F
G +∞
选择路径D - F
A 0
B 8 A - C - B
C 2 A - C
D 4 A - C - D
E 9 A - C - B - E
F 10 A - C - D - F
G +∞
选择路径E - F,不更新
A 0
B 8 A - C - B
C 2 A - C
D 4 A - C - D
E 9 A - C - B - E
F 10 A - C - D - F
G +∞
选择路径E - G
A 0
B 8 A - C - B
C 2 A - C
D 4 A - C - D
E 9 A - C - B - E
F 10 A - C - D - F
G 16 A - C - B - E - G
选择路径F - G
A 0
B 8 A - C - B
C 2 A - C
D 4 A - C - D
E 9 A - C - B - E
F 10 A - C - D - F
G 14 A - C - D - F - G
以上操作属于一轮，要遍历以上操作，直到所有顶点权值都不再更改。
第二轮可将B的值遍历为7，E从9变成8.
第三轮更新之后，所有顶点的权重都不再更新.
...
最终的结果是 A - G 权重是14 ，最短路径是A - C - D - F - G
网友评论