SPFA——Shortest Path Faster Algorithm,可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径,可以处理负边。SPFA的实现甚至比Dijkstra或者Bellman_Ford还要简单:

设Dist代表S到I点的当前最短距离,Fa代表S到I的当前最短路径中I点之前的一个点的编号。开始时Dist全部为+∞,只有Dist[S]=0,Fa全部为0。

维护一个队列,里面存放所有需要进行迭代的点。初始时队列中只有一个点S。用一个布尔数组记录每个点是否处在队列中。

每次迭代,取出队头的点v,依次枚举从v出发的边v->u,设边的长度为len,判断Dist[v]+len是否小于Dist[u],若小于则改进Dist[u],将Fa[u]记为v,并且由于S到u的最短距离变小了,有可能u可以改进其它的点,所以若u不在队列中,就将它放入队尾。这样一直迭代下去直到队列变空,也就是S到所有的最短距离都确定下来,结束算法。若一个点入队次数超过n,则有负权环。

以上来自一个传说当中大牛们神出鬼没的地方,它的名字叫做NOCOW。

以下是我的代码。

inq表示是否在队列内,next[v]和l[i]表示以v为顶点的边链表。E代表边的存储数组。

 

void spfa ( int src )
{
    memset ( inq, 
0x00sizeof ( inq ) );
    q.push ( src );
    inq[src] 
= 1;
    dist[src][src] 
= 0;
    
while ( !q.empty () )
    
{
        
int u = q.front ();
        inq[u] 
= 0;
        q.pop ();
        
int i = next[u];
        
while ( i != -1 )
        
{
            
if ( dist[src][u] + E[i].d < dist[src][E[i].v] )
            
{
                dist[src][E[i].v] 
= E[i].d + dist[src][u];
                
if ( inq[E[i].v] == 0 )
                
{
                    inq[E[i].v] 
= 1;
                    q.push ( E[i].v );
                }

            }

            i 
= l[i];
        }

    }

}