SPFA算法及其应用和优化

SPFA算法及其应用和优化

by mps

【问题引入】

  又是一年春运时，因为睡懒觉而导致抢不到票的你，只能打车回家了，而无疑会消耗许多钱财（黑车...），为了尽可能的节省钱，你希望走的是最短路，路途中会经过n个城市，而你每次经过两个城市之间的高速公路时，都会损耗C_i元，假设其中包含了所有的价钱（邮费，过桥费之类的），你现在在1号城市，希望到达n号城市去，请问最少花费是多少？

【输入描述】

  第一行，n,m，表示有n个城市,m条高速公路

  第二行至第m+1行，每行三个数u,v,w，表示u城市到达v城市的耗费为w元（均为有向边）

【数据范围】

  对于20%的数据，n≤100,m≤1,000

  对于50%的数据，n≤1,000, m≤1,000

  对于100%的数据，n≤10,000,m≤10,000

【分析】

  题目其实并不难，一个最短路的裸模板题目

  但是数据却让初学者犯了难，很明显出题人的意思是这样的：

  对于20分，是留给只会floyd的人

  对于50分，是留给会dijkstra或者bellman_ford

  对于100分，是留给会heap+dijkstra或者spfa+(slf/lll)

  本文着重介绍SPFA以及优化（SLF/LLL)

  参考资料：http://www.cnblogs.com/pony1993/archive/2012/09/07/2675654.html  

  SPFA算法是基于Bellman_ford算法的改进，Bellman_ford算法的大致模板如下：

  for(i=1->v)

    for(j=1->e)

         if(u,v (-E 且 e(u,v)+δu<δv)

           δv=e(u,v)+δu

    时间复杂度O(ve)

   对于数据较大的情况（比如说例题）会TLE，所以我们需要优化

   那么如何优化呢？

   我们发现，每次没有必要松弛m条边，只需要松弛与当前节点有关的边即可，但是又会有些节点脱离了拓扑关系，所以我们可以采用队列/栈来维护拓扑关系

   这样我们的时间复杂度就降到了O(VK) 一般情况下k<2，但没有绝对性的证明而且有针对性数据，所以除非迫不得已采用SPFA（事实上出现迫不得已的情况就是因为出题人想让你用SPFA....）否则尽可能的采用高效率的Dijkstra，实在不行弄个堆优化，要知道，堆优化的dijkstra是可以超过SPFA的（而且绝对稳定）

   而SPFA用手动队列写起来有点烦，而我们C++的福利就在于STL为我们提供了绝对具有安全性的队列，但是耗时间太长了，不过我们可以采用许多优化来弥补

   具体有4种优化方案（1,3只能选1种）

  （1）SLF

    设当前队头为i，即将入队的点j，若δi≥δj，则直接将j入对头，否则入队尾，效率提升10%~20%，需要数据结构双端队列

  （2）LLL（效率低下，这里不赘述）

  （3）Prq

    采取优先队列，每次存储距离小的，效率提升20%~30%,与堆优化的dijkstra并肩

  （4）Math（适用于判断负权环）

    由于K的取值不定，有可能会非常多，所以对于判断负权环就只能无奈的TLE了，这时我们可以用随机数生成一个在题目条件下的最大最极端的数据，然后不断地缩小N

   （补充：判断是否具有负权环只需判断每个点的入队次数是否＞N）

   到最后原本O(1000*1000)的算法可能优化为O（1000*3）的算法，不过本优化适宜RP好或者数学学霸使用

   推荐练习题：

   NOIP2014D2T2寻找道路

   USACO 欢乐派对

   USACO 骑马修栅栏

   另：最短路学好对以后的网络流问题有极大的帮助