图论part10 bellman_ford算法
- bellman_ford算法：对所有边进行松弛N-1次操作，求得目标最短路
卡码网94：寻找从节点1到节点n的最短路径并计算路径总权值，输出权值；不存在路径输出unconnected
- 松弛
状态一： minDist[A] + value 可以推出 minDist[B]
状态二： minDist[B]本身就有权值 （可能是其他边链接的节点B 例如节点C，以至于 minDist[B]记录了其他边到minDist[B]的权值）
对状态一二进行选择得过程就叫松弛
if (minDist[B] > minDist[A] + value) minDist[B] = minDist[A] + value
- 为什么松弛n-1次？
只要知道松弛一次得到的是到达和起点一条边相连得节点最短距离
到达节点n的最短距离就能通过松弛n-1次得到，同时还能得到到所有节点的最短距离
- 不能从未计算过路径的节点出发
- SFPA算法
适用队列优化bellman_ford，简单来记就是邻接表存图（维护边），BFS，并使用标记数组对目标节点进行标记，但是需要有取消标记的操作
- 判断负权回路，由该系列算法可知我们通过n-1次松弛可以得到从起点到任意一点的最少开销，如果存在负权回路，再继续松弛，就是沿着该回路绕圈，会使开销越来越小。判断方法就是松弛n-1次后在松弛一次看minDist数组有没有变化
