代码随想录冲冲冲 Day58 图论Part9

47. 参加科学大会（第六期模拟笔试）

根据昨天的dijkstra进行堆优化

使用的原因是点多但边少 所以直接对于边进行操作

1.对于priority_queue来说

这是最小堆, 小于的话就是最大堆

之后由于是根据边来说的 所以新建一个Edge并且初始化一下

之后由于使用了priority_queue来构造最小堆，在加上传入queue中的都是一个点以及点到原点的距离，根据自定义的判断公式，已经默认排好了最小也就是离得最近的。所以每次只要top后 pop掉就可以了

下面的判断是为了避免1 -> 2 -> 3 ->1这种的成环情况

之后就是去更新值 在更新完之后会把还没有访问到的 cur的邻边放入queue中

卡码网KamaCoder

94. 城市间货物运输 I

bellman_ford算法 使用场景是图中有负权重时可以使用

1.什么是松弛

每条边有起点、终点和边的权值。例如一条边，节点A 到 节点B 权值为value，如图：

minDist[B] 表示 到达B节点 最小权值，minDist[B] 有哪些状态可以推出来？

状态一： minDist[A] + value 可以推出 minDist[B] 状态二： minDist[B]本身就有权值 （可能是其他边链接的节点B 例如节点C，以至于 minDist[B]记录了其他边到minDist[B]的权值）

minDist[B] 应为如何取舍。

本题我们要求最小权值，那么 这两个状态我们就取最小的

if (minDist[B] > minDist[A] + value) minDist[B] = minDist[A] + value

也就是说，如果 通过 A 到 B 这条边可以获得更短的到达B节点的路径，即如果 minDist[B] > minDist[A] + value，那么我们就更新 minDist[B] = minDist[A] + value ，这个过程就叫做 “松弛” 。

对所有边松弛一次，相当于计算 起点到达 与起点一条边相连的节点 的最短距离。

如图有n个节点 就松弛n-1次

然后基于

if (minDist[from] != INT_MAX && minDist[to] > minDist[from] + price) { minDist[to] = minDist[from] + price; 

这个核心公式继续更新

另外一点是如果松弛次数大于了n-1就不会继续更新了