求最短路径的算法有许多种，除了排序外，恐怕是OI界中解决同一类问题算法最多的了。最熟悉的无疑是Dijkstra，接着是Bellman-Ford，它们都可以求出由一个源点向其他各点的最短路径；如果我们想要求出每一对顶点之间的最短路径的话，还可以用Floyd-Warshall。

SPFA是这篇日志要写的一种算法，它的性能非常好，代码实现也并不复杂。特别是当图的规模大，用邻接矩阵存不下的时候，用SPFA则可以很方便地面对临接表。每个人都写过广搜，SPFA的实现和广搜非常相似。

如何求得最短路径的长度值？

首先说明，SPFA是一种单源最短路径算法，所以以下所说的“某点的最短路径长度”，指的是“某点到源点的最短路径长度”。

我们记源点为S，由源点到达点i的“当前最短路径”为D[i]，开始时将所有D[i]初始化为无穷大，D[S]则初始化为0。算法所要做的，就是在运行过程中，不断尝试减小D[]数组的元素，最终将其中每一个元素减小到实际的最短路径。

过程中，我们要维护一个队列，开始时将源点置于队首，然后反复进行这样的操作，直到队列为空：

(1)从队首取出一个结点u，扫描所有由u结点可以一步到达的结点，具体的扫描过程，随存储方式的不同而不同；

(2)一旦发现有这样一个结点，记为v，满足D[v] > D[u] + w(u, v)，则将D[v]的值减小，减小到和D[u] + w(u, v)相等。其中，w(u, v)为图中的边u-v的长度，由于u-v必相邻，所以这个长度一定已知（不然我们得到的也不叫一个完整的图）；这种操作叫做松弛。

引用内容

松弛操作的原理是著名的定理：“三角形两边之和大于第三边”，在信息学中我们叫它三角不等式。所谓对i,j进行松弛，就是判定是否d[j]>d[i]+w[i,j]，如果该式成立则将d[j]减小到d[i]+w[i,j]，否则不动。

(3)上一步中，我们认为我们“改进了”结点v的最短路径，结点v的当前路径长度D[v]相比于以前减小了一些，于是，与v相连的一些结点的路径长度可能会相应地减小。注意，是可能，而不是一定。但即使如此，我们仍然要将v加入到队列中等待处理，以保证这些结点的路径值在算法结束时被降至最优。当然，如果连接至v的边较多，算法运行中，结点v的路径长度可能会多次被改进，如果我们因此而将v加入队列多次，后续的工作无疑是冗余的。这样，就需要我们维护一个bool数组Inqueue[]，来记录每一个结点是否已经在队列中。我们仅将尚未加入队列的点加入队列。


算法能否结束？

对于不存在负权回路的图来说，上述算法是一定会结束的。因为算法在反复优化各个最短路径长度，总有一个时刻会进入“无法再优化”的局面，此时一旦队列读空，算法就结束了。然而，如果图中存在一条权值为负的回路，就糟糕了，算法会在其上反复运行，通过“绕圈”来无休止地试图减小某些相关点的最短路径值。假如我们不能保证图中没有负权回路，一种“结束条件”是必要的。这种结束条件是什么呢？

思考Bellman-Ford算法，它是如何结束的？显然，最朴素的Bellman-Ford算法不管循环过程中发生了什么，一概要循环|V|-1遍才肯结束。凭直觉我们可以感到，SPFA算法“更聪明一些”，就是说我们可以猜测，假如在SPFA中，一个点进入队列——或者说一个点被处理——超过了|V|次，那么就可以断定图中存在负权回路了。


最短路径本身怎么输出？

在一幅图中，我们仅仅知道结点A到结点E的最短路径长度是73，有时候意义不大。这附图如果是地图的模型的话，在算出最短路径长度后，我们总要说明“怎么走”才算真正解决了问题。如何在计算过程中记录下来最短路径是怎么走的，并在最后将它输出呢？

Path[]数组，Path[i]表示从S到i的最短路径中，结点i之前的结点的编号。注意，是“之前”，不是“之后”。最短路径算法的核心思想成为“松弛”，原理是三角形不等式，方法是上文已经提及的。我们只需要在借助结点u对结点v进行松弛的同时，标记下Path[v] = u，记录的工作就完成了。

输出时可能会遇到一点难处，我们记的是每个点“前面的”点是什么，输出却要从最前面往最后面输，这不好办。其实很好办，见如下递归方法：

程序代码

void PrintPath(int k){
    if( Path[k] ) PrintPath(Path[k]);
    fout<<k<<' ';
}

SPFA的代码怎么写？

我写了邻接表和邻接矩阵两种，两者想像起来是那么的不同，算法的思路上实在区别不大，只是用不同方式诠释“扫描”的过程而已。只给出SPFA的单个函数，我不觉得很容易看懂，但是我仍然把两个程序的SPFA函数放在下面。在日志的结尾处，有一个完整版文件下载。贴程序，首先是邻接表的：

程序代码

void SPFA(){
    for(int i=1; i<=gv; i++)
        Dist[i] = 100000;
    Dist[S] = 0;
    int closed = 0, open = 1;
    queue[1] = S;
    Inqueue[S] = true;
    do{
        closed++;
        node *tmp = connect[queue[closed]];
        Inqueue[queue[closed]] = false;
        while(tmp != NULL){
            if( Dist[tmp->key] > Dist[queue[closed]] + tmp->w ){
                Dist[tmp->key] = Dist[queue[closed]] + tmp->w;
                Path[tmp->key] = queue[closed];
                if( !Inqueue[tmp->key] ){
                    Inqueue[tmp->key] = true;
                    open++;
                    queue[open] = tmp->key;
                }
            }
            tmp = tmp->next;
        }
    }while(closed < open);
}

然后是邻接矩阵的：

程序代码

void SPFA(){
    for( int i=1; i<=gv; i++){
        Dist[i] = 100000;
        for( int j=1; j<=gv; j++)
            if( !Graph[i][j] && i!=j) Graph[i][j] = 100000;
    }
    int closed = 0, open = 1;
    queue[1] = S;
    Dist[S] = 0;
    do{
        closed++;
        int u = queue[closed];
        Inqueue[u] = false;
        for(int i=1; i<=gv; i++)
            if ( Dist[i] > Dist[u] + Graph[u][i] ){
                Dist[i] = Dist[u] + Graph[u][i];
                Path[i] = u;
                if( !Inqueue[i] ){
                    Inqueue[i] = true;
                    open++;
                    queue[open] = i;
                }
            }
    }while(closed < open);
}

spfa算法 Easy sssp 收藏
输入数据给出一个有N(2 <= N <= 1,000)个节点，M(M <= 100,000)条边的带权有向图.
要求你写一个程序, 判断这个有向图中是否存在负权回路. 如果从一个点沿着某条路径出发, 又回到了自己, 而且所经过的边上的权和小于0, 就说这条路是一个负权回路.
如果存在负权回路, 只输出一行-1;
如果不存在负权回路, 再求出一个点S(1 <= S <= N)到每个点的最短路的长度. 约定: S到S的距离为0, 如果S与这个点不连通, 则输出NoPath.

INPUT:
第一行: 点数N(2 <= N <= 1,000), 边数M(M <= 100,000), 源点S(1 <= S <= N);
以下M行, 每行三个整数a, b, c表示点a, b(1 <= a, b <= N)之间连有一条边, 权值为c(-1,000,000 <= c <= 1,000,000)

OUTPUT:
如果存在负权环, 只输出一行-1, 否则按以下格式输出
共N行, 第i行描述S点到点i的最短路:
如果S与i不连通, 输出NoPath;
如果i = S, 输出0;
其他情况输出S到i的最短路的长度

INPUT:
6 8 1
1 3 4
1 2 6
3 4 -7
6 4 2
2 4 5
3 6 3
4 5 1
3 5 4

OUTPUT:
0
6
4
-3
-2
7

注意：
题目说的不是很清楚，给出的图不一定是完全联通图，有些是断开的几个图，所以在判断的源点是否有环以外还要分别对不同的点进行spfa呀。再进行分别的判断和输出。

有几个优化：
1.可以先判断是否有负权自环，有则直接输出-1
2.在枚举的过程中，当这个顶点的最短路(d[i])<0时，有负权回路，输出-1.

【参考程序】：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
long queue[1001],a[1001],psum[1001],dis[1001],l[1001][1001],cost[1001][1001];
long n,m,s,i,j;
bool hash[1001],bk;
void spfa(int s)
{
    int head,tail,start,now,i;
    for (i=1;i<=n;i++)
    {
        dis[i]=0xfffffff;
        psum[i]=0;
        hash[i]=false;
    }
    head=tail=1;hash[s]=true;
    psum[s]=1;dis[s]=0;queue[1]=s;
    while (head<=tail)
    {
        start=queue[(head-1)%n+1];
        hash[start]=true;
        for (i=1;i<=l[start][0];i++)
        {
            now=l[start][i];
            if (dis[now]>dis[start]+cost[start][now])
            {
                dis[now]=dis[start]+cost[start][now];
                if (!hash[now])
                {
                    hash[now]=true;
                    tail++;
                    queue[(tail-1)%n+1]=now;
                    psum[now]++;
                    if (psum[now]>n)
                    {//记录每个点进队的次数(判断环的关键}
                        bk=false;
                        return;
                    }
                }
            }
        }
        head++;
        hash[start]=false;
        if (dis[s]<0)
        {//判断环的一个优化
            bk=false;
            return;
        }
    }
}
void output()
{
    bk=true;
    spfa(s);
    if (!bk)
    {
        printf("-1\n");
        return;
    }
    memcpy(a,dis,sizeof(long)*(n+1));
    for (i=1;i<=n;i++)
      if (a[i]==0xfffffff)
      {
            bk=true;
            spfa(i);
            if (!bk)
            {
                printf("-1\n");
                return;
            }
      }
    for (i=1;i<=n;i++)
      if (a[i]==0xfffffff) printf("NoPath\n");
      else printf("%d\n",a[i]);
}
void input()
{
    scanf("%d%d%d",&n,&m,&s);
    for (i=1;i<=n;i++)
      for (j=1;j<=n;j++)
        if (i==j) cost[i][j]=0;
        else cost[i][j]=0xfffffff;
    memset(l,0,sizeof(l));
    int x,y,c;
    for (i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        if (c<cost[x][y])
        {
            cost[x][y]=c;
            l[x][0]++;
            l[x][l[x][0]]=y;
        }
    }
}
int main()
{
    input();
    output();
    system("pause");
    return 0;
}

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/bobcowwocb/archive/2009/09/14/4550188.aspx

SPFA算法模版+邻接表实现

SPFA即shotest path faster algorithm，由意思就可以看出该算法效率比较高。

其实SPFA就是bellman-ford算法的一个优化。

具体做法是用一个队列保存待松弛的点，然后对于每个出队的点依次遍历每个与他有边相邻的点（用邻接表效率较高），如果该点可以松弛并且队列中没有该点则将它加入队列中，如此迭代直到队列为空。

据说平均效率是O（E），可见对边稀疏的图用此算法效果是相当可观的。

 

若要判负环路,则记录一个点的入队次数,若超过边数，则有负权环。

 

#include <iostream>
#include <queue>
using namespace std;

const long MAXN=10000;
const long lmax=0x7FFFFFFF;

typedef struct  
{
    long v;
    long next;
    long cost;
}Edge;


Edge e[MAXN];
long p[MAXN];
long Dis[MAXN];
bool vist[MAXN];

queue<long> q;

long m,n;//点,边
void init()
{
    long i;
    long eid=0;

    memset(vist,0,sizeof(vist));
    memset(p,-1,sizeof(p));
    fill(Dis,Dis+MAXN,lmax);

    while (!q.empty())
    {
        q.pop();
    }

    for (i=0;i<n;++i)
    {
        long from,to,cost;
        scanf("%ld %ld %ld",&from,&to,&cost);

        e[eid].next=p[from];
        e[eid].v=to;
        e[eid].cost=cost;
        p[from]=eid++;

        //以下适用于无向图
        swap(from,to);
        
        e[eid].next=p[from];
        e[eid].v=to;
        e[eid].cost=cost;
        p[from]=eid++;

    }
}

void print(long End)
{
    //若为lmax 则不可达
    printf("%ld\n",Dis[End]);    
}

void SPF()
{

    init();

    long Start,End;
    scanf("%ld %ld",&Start,&End);
    Dis[Start]=0;
    vist[Start]=true;
    q.push(Start);

    while (!q.empty())
    {
        long t=q.front();
        q.pop();
        vist[t]=false;
        long j;
        for (j=p[t];j!=-1;j=e[j].next)
        {
            long w=e[j].cost;
            if (w+Dis[t]<Dis[e[j].v])
            {
                Dis[e[j].v]=w+Dis[t];
                if (!vist[e[j].v])
                {
                    vist[e[j].v]=true;
                    q.push(e[j].v);
                }
            }
        }
    }

    print(End);

}

int main()
{
    while (scanf("%ld %ld",&m,&n)!=EOF)
    {
        SPF();
    }
    return 0;
}

0

0

0

(请您对文章做出评价)