day60 | bellman优化

优化一 用队列

• 每次的松弛过程中，我们不用对所有的边进行遍历，只需要对上一次松弛过后的能达到的点的集合进行遍历
• 维护一个点集合， 每次松弛过后便把 to 节点加入到这个集合中。 每次松弛找的边都需要在这个点集合里面的点为开始
• 既然是一个集合要避免重复加入

变形二 判断负环

• 判断 n-1 次必定能达到end，那么再判断一次，如果出现负环则路径会继续更行。

变形二 判断 k 次

至多经过 k 次城市可以达到的最短距离。 显然只需要松弛k+1次即可

• 一个问题是松弛的过程中我们会对所有的边进行松弛，他们的先后顺序导致了我们松弛次数和实际经过节点个数的区别
• 举个例子就是当边的先后顺序很好的时候一次遍历即可得到最短路径，但他可能经过了所有的节点。
• 为了避免在一次松弛过程中出现这样的情况，我们对 需要维护好上一次mindist的数组不被这次污染，从而避免在一次松弛中经过了计算了多个 edge 相加造成的路径