dijkstra/SPFA算法的正确性本质

回顾 $dijkstra$ 算法的思想，他是基于贪心的：对于寻找单源最短路，每次找到全图 $dist$ 最小的那个点来更新其他点

1.为什么$dijkstra$求最短路只能在正权图上使用？

因为保证 $dijkstra$ 算法的贪心确认了每个点只会被更新一次，如果是最短路的话，正权图 $dist$ 只会越来越大，所以能保证这个性质。

但是对于负权图， $dist$ 不一定是单调增大的，因此这个点不能被确认已经是最终 $dist$ 最小的情况。

【总结】最短路使用 $dijkstra$ 算法要保证边权全部为正才能保证每个点只被更新一次

2.对于最长路，能否使用$dijkstra$算法？

只要理解了 $dijkstra$ 算法的贪心原理，就能发现对于最长路也是可以运算的。

• 对于最短路，我们要保证边是正的递增，才能保证每次找到的最小的 $dist$ 再也不会被更新掉

• 那么对于最长路，我们只要保证 $dist$ 是越来小的，才能保证每次我们找到的最大的距离点再也不会被更新掉

那么边权的加肯定是不满足的，什么是满足的？

AcWing 1126. 最小花费 - AcWing的边权的乘积，而且是 $0\sim 1$ 的边权，能保证 $dist$ 越来越小

3.$SPFA$ 算法是否可以处理最长路问题？

答案是可以的，因为SPFA比较牛逼，因为 $SPFA$ 算法的正确性来源于松弛操作，也就是那个三角不等式迭代更新所有的边，这个操作不管正的负的乘的都可以实现，所以最长路也是照样能做的！

这么牛逼活该被卡