Bellman-Ford算法用于路由计算

Bellman-Ford路由算法

算法描述

1. 初始化阶段，构建距离数组d[]与前驱节点数组pred[]，其中d[s]的初始值设为0，其余节点的初始距离设置为无穷大；pred数组用于记录各节点的前驱节点，s表示算法的起始节点。

2. 迭代计算过程：对边集合E中的每条边依次执行松弛操作，通过多次迭代逐步优化顶点集合V中每个顶点v的最短路径估计值，使其逐渐趋近于真实的最短路径长度；该过程需重复进行|V|-1次。

3. 检测负权环路：检查边集合E中的每条边两端顶点的距离是否已达到稳定状态。若存在尚未收敛的顶点，则判定当前图中存在负权环路，算法返回false以表示问题无解；反之，若所有可达顶点均完成收敛，则算法返回true，并将源点s到各可达顶点v的最短路径长度存储在d[v]中。

输入：

6
10
0
0 1 2 3 4 5
0 1 -10
0 4 19
0 5 21
1 2 5
1 3 6
1 5 11
2 3 -6
3 4 18
3 5 14
4 5 -33

输出：

从起点s=0出发至节点0的最短距离为0：