代码随想录冲冲冲 Day59 图论Part10
94. 城市间货物运输 I
这是基于之前Bellman_ford算法的一个优化，之前讲到可以通过n-1次来完全松弛得到答案
但是其实每次并不是所有的点都要去松弛
只针对mindist值修改过的进行修改就可以了
同时进一步优化就是让已经在队列里的 被忽略就可以了
卡码网KamaCoder
95. 城市间货物运输 II
这是再讲如果图中出现负权和的情况 怎么解决
如果是负权和了 那么Bellman_ford在n-1次松弛之后 数值依旧会变化
这里有两种方法判断是否有环
1.直接松弛n次，在第n次观察是否还会变化 如果还会变化就是有环
2.在que的基础上记录每个点的松弛次数 如果出现松弛次数=n 说明一定有环
卡码网KamaCoder
卡码网KamaCoder
96. 城市间货物运输 III
那么在负环和并且规定了最多经过的节点数 也就是松弛次数
所以需要一个minDist_copy去把上一次的保存下来用来跟新
对于SPFA也是一样 用一个变量 que_size 记录每一轮松弛入队列的所有节点数量。
下一轮松弛的时候，就把队列里 que_size 个节点都弹出来，就是上一轮松弛入队列的节点