若读者还不太了解SPFA算法，指路一篇博客：https://blog.csdn.net/hzf0701/article/details/107691013
关于SPFA算法，它已经死了，很多出题人都会故意卡SPFA算法，所以我们若进行优化，说不定就能过呢。但u1s1，对于正权图来说，还是老老实实用Dijkstra算法吧，贼香！

进入正题：我们以vector模拟邻接表存储为例。（哪种都一样，只是存储方式不同而已，主要是算法中心思想）

先介绍基本结构信息：

SLF优化，即Small Label First策略，使用STL中的双端队列deque容器来实现，较为常用。

这个顾名思义就是在原有的SPFA算法中每次出队进行判断扩展出的点与队头元素进行判断，若小于进队头，否则入队尾。即：对要加入队列的点 u，如果 dist[u] 小于队头元素 v 的 dist[v]，将其插入到队头，否则插入到队尾。

注：队列为空时直接插入队尾。

LLL优化即：Large Label Last策略。顾名思义就是大的放后面，这个不是针对要入队的元素，而是针对要出队的元素，我们是这样子来处理的：设队首元素为 temp ，每次松弛时进行判断，队列中所有 dis 值的和为sum，队列元素为num 。

若 dist[ temp] *num>sum ，则将 temp 取出插入到队尾，查找下一元素，直到找到某一个 temp 使得 dis[ temp ]*sum <= x ，则将 temp出队进行松弛操作。

我们根据前面得知SLF是对入队顶点进行判断，LLL是对出队顶点判断的，两者互不影响，那么不就可以结合了吗？

我们知道SPFA算法是利用BFS的思想的，由于采用广度优先的思想，每当我们扩展出一个新的节点，总是把它放到队列的末尾，其缺点是中断了迭代的连续性。而实际上如果采用深度优先的思想，我们可以直接从这个新节点继续往下扩展，则我们就可以不断递归进行求解。我们用DFS的思想来代替BFS，这就是DFS优化。可这样优化真的好吗？这种优化常常用于判断正/负环，时间复杂度可以达到O(m)（m是边）。思路是，我们每一次dfs的时候如果走回之前dfs过的点，那就是有环，除了这个dfs的标记，我们还可以打另一个vis数组记录更新过权值的节点，以后就不必重复更新，大大降低复杂度。如果只是要求最短路径，还是使用前三种优化吧。用DFS优化我们要使用一个访问数组来判断一个点是否再次走过，不同于上面的visited。

我们先要进行初始化，注意：绝对不能放在spfa_dfs函数中。

以上为博主自己整理，自己测试都没有问题的。若有任何疑问都可以私信我或者在评论区留言，我都会给予回复，愿能帮助到你。