带负权的无负环最短路问题

对于一张有负边权的图，普通 Dijkstra 就不能用了，比如：

正常的 Dijkstra 扩散的节点依次为 $1,3,2,4$。
这时候可以发现，当点 $2$ 扩散的时候，原本达到点 $3$ 的路径长度是 $1$，路径 $1⟶2⟶3$ 的权值之和为 $-2$，明显更短，这个时候点$1$ 到点 $3$ 的路径长度就会被更新为 $-2$，但是，点 $3$ 在点 $2$ 之前已经被扩散过，不会在进行第二次扩散。此时，点 $1$ 到点 $4$ 的路径长度依旧是 $1+2=3$。

这里说明了 Dijkstra 的一个缺陷，贪心思路会考虑不到后续的负数。

那么，我们可以对 Dijkstra 做一个改动，解决现在遇到的问题。
上述的问题发生的根源就是 $vis$ 数组，在当前点找到更优值的时 $vis$ 数组不会改变，就导致了上图中点 $4$ 没有被更新，所以我们在找到更优值时就再给当前点一个机会。

if(dis[y]>dis[x]+z){vis[y]=0;dis[y]=dis[x]+z;
}

这样可以很好地解决上图中出现的问题，但是判断负环还是需要 SPFA
那么，我们将上述的改动版 Dijkstra 命名为SPstra

带负环的最短路问题

这个时候就可以考虑用到 SPFA。
SPFA 与 Dijkstra 的不同点：

入队条件

Dijkstra 的遍历概念是：扩散
而 SPFA 的遍历概念是：挑选
SPFA 的标记表示的是“是否在队列中”，也就是说有没有看过这个元素值更新后对相连点的影响。
如果没有在队列中，并且还找到了当前点更优的方案，那么当前点就该入队上班了。（可以借助文章最顶上的图来理解）。

出队标记

出队后，元素就不在队列中了，标记取消。

负环判断

负环是什么？
负环就是一个有向图中的环，并且对这个环遍历一圈得到的权值总和为负，那么这个时候就可以一直绕着这个环转圈圈，使权值总和越来越小。
我们假设：一张有 $n$ 个点的有向图中有这样一个点 $x$，这个点十分有魅力，图中其余的 $n-1$ 个点都有一条边连向这个点。

再极端一点，这其余的 $n-1$ 个点按照被遍历到的顺序依次对点 $x$ 有更优贡献。
那么，这个点就会被入队 $n-1$ 次，这个时候还没有出现负环。
但是，如果这个点再被入队一次，入队次数达到了 $n$ 次，就一定有一个点（暂且称为点 $y$）连接点 $x$ 的这条路径被遍历了两次，这个时候就有了负环，因为点 $x$ 在被点 $y$ 连接的情况下还有一条负数边权和的路径连接着点 $y$。

SPFA 可否使用优先队列优化

其实使用优先队列优化的 SPFA 就是前面的 “SPstra” 加上一个负环判断。

对于这个问题，答案是：能，但是很极端。

SPFA 优先队列优化的适用场景

对于正边权居多的图，可以使用优先队列优化，这样可以使效率接近 Dijkstra 的 $O(N\log N)$。

普通 SPFA 的适用场景

对于负边权居多的图，其实普通队列和优先队列的遍历次数都是差不多的，只是顺序变了，而且优先队列还多了一个 $O(\log N)$，效率还不如普通队列。

总结

考试或者比赛时，题目的数据我们无从得知。
但我们知道的是，造数据的人们都是阴险狡诈忠恳善良的，我们可以猜疑相信他们。