关于图论【最短路径之Bellman_ford 算法（队列优化）|卡码网94.城市间货物运输的思考】

目录

二、本题代码

三、关键思路

四、优化原因

五、注意事项

// 展示完整题目

二、本题代码

// 展示完整代码

三、关键思路

1、用队列把当前遍历节点所指向的节点记录到队列里，更新在队列里的松弛有意义的节点的最短距离

四、优化原因

1、因为单纯的Bellman_ford算法会进行很多次无意义的松弛

（比如一开始的时候，只有起点1所指向的节点能更新最短距离，但是第一条输入的边是5 6 -2，这个时候起点1和结点5根本就没有相连，所以就算进行了一次循环，也不会做任何操作，就浪费了时间）

2、时间复杂度更低

五、注意事项

1、邻接表在定义的时候要先写好数组的位置个数

2、邻接表在加入结构体的时候要push_back(结构体名(成员变量1,成员变量2))

// 注意这个结构体名要写出来