Bellman ford 最短路径算法
Bellman ford 最短路径算法
下表记录S到每个节点的距离：
第一次迭代，
S->A = 4 ，因为S->A目前为INF，因此更新MIN(S->A)为4
S->B = 6，因为S->B目前为INF，因此更新MIN(S->B)为6
S->C=INF（表示不可达）
S->D=INF
MIN(S->S) | MIN(S->A) | MIN(S->B) | MIN(S->C) | MIN(S->D) |
0 | 4 | 6 | INF | INF |
第二次从A开始迭代：
A->C=3，因为S->C目前为INF，因此更新MIN(S->C)为7
MIN(S->S) | MIN(S->A) | MIN(S->B) | MIN(S->C) | MIN(S->D) |
0 | 4 | 6 | 7 | INF |
第二次从B开始迭代，
B->A= -5 ,因为S->A=4 S->B=6，因此S->B->A=1 < S->A = 4，故更新MIN(S->A)=1
因为更新了S->A，而A可达点集有C，因此需要对这些可达点集进行递归：
MIN(S->C) 此时为7，而MIN(S->A)->C为1+3=4，故需要更新MIN(S->C)=4
B->D = 1，因为MIN(S->D) = INF，故MIN(S->D)需更新为7
MIN(S->S) | MIN(S->A) | MIN(S->B) | MIN(S->C) | MIN(S->D) |
0 | 1 | 6 | 4 | 7 |
从C点开始迭代：
C可达点集只有D，因为MIN(S->D)为7，而MIN(S->C)->D为4+2=6，因此MIN(S->D)需要更新为6
得到最后结果为：
MIN(S->S) | MIN(S->A) | MIN(S->B) | MIN(S->C) | MIN(S->D) |
0 | 1 | 6 | 4 | 6 |