C++图论基础单源最短路四种算法总结

基于贪心策略：

        每次拿出还未确定最短路的点中，距离起点最近的点；

        打上标记；

        打上标记之后，跟新刚刚打上标记的点的出边连接的点的最短路。

—真实的情况只需要执行 n – 1 次，最后没有出边的点实际不需要再执行单趟操作，但是，如果在跑算法的过程中，跟新累加结果，只单单执行 n – 1 次是不够的，所以，我们为了保险，均执行 n 次~

使用堆优化找点操作：

        把还没有确定最短路的点扔进堆中，方便找距离起点最近的点。

暴力松弛：

        执行 n – 1 轮松弛操作；

        单趟扫描所有的边看看能不能松弛。

—bool 类型的 flag 还可以进行一定的优化，因为并不是每个图都必须跑满 n – 1 轮松弛操作才能找到最短路。

使用队列优化bellman-ford 算法：

        只有上一轮被松弛的点，下一轮才有可能引起松弛操作。

—队列就是维护这些实际可以引起松弛操作的点；spfa 算法中的 st 数组是标记哪些点在队列中；队列维护的点不能有重复–该点在从队列中拿出时，是可以拿到最新值的。

失效

        出现负边权时贪心策略不正确

可以判断负环：

        存在负环，BF算法就可以超出 n – 1 轮的限制，执行超过 n – 1 轮松弛操作；

        执行 n 轮，判断是否有松弛操作。

可以判断负环：

        存在负环，while 循环会死循环；

        创建 cnt 数组，给每个节点都配上一个“记边器”，标记从起点到该点的边数，每跟新一个节点，实时判断是大于 n – 1 条边存在负环，还是小于等于 n – 1 存在最短路，不存在负环。