SPFA

　

spfa

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1010;
const int INF = 1000000;
int path[maxn];
int dis[maxn];
int inq[maxn];
int shortest[maxn];
int n,m;
queue<int> q;
struct Edge{
    int to;
    int w;
};
vector<Edge> ve[maxn];
void SPFA(int v0){
    int u;
    memset(inq,0,sizeof(inq));
    for(int i=0;i<n;i++){
        dis[i]=INF;
        path[i]=v0;
    }
    dis[v0]=0;
    while(!q.empty())
        q.pop();
    q.push(v0);
    inq[v0]++;
    while(!q.empty()){
        u=q.front();
        q.pop();
        inq[u]--;
        for(int i=0;i<ve[u].size();i++){
            if(dis[ve[u][i].to]>dis[u]+ve[u][i].w){
                dis[ve[u][i].to]=dis[u]+ve[u][i].w;
                path[ve[u][i].to]=u;
                if(!inq[ve[u][i].to]){
                    q.push(ve[u][i].to);
                    inq[ve[u][i].to]++;
                }
            }
        }
    }

}
int main(){
    int u,v,w;
    Edge e;
    while(scanf("%d%d",&n,&m)!=EOF){
        for(int i=0;i<m;i++){
            scanf("%d%d%d",&u,&v,&w);
            e.to=v;e.w=w;
            ve[u].push_back(e);
        }
        SPFA(0);
        for(int i=1;i<n;i++){
            printf("%d: %d   ",i,dis[i]);
            memset(shortest,0,sizeof(shortest));
            int k=0;
            shortest[k]=i;
            while(path[shortest[k]]!=0){
                k++;
                shortest[k]=path[shortest[k-1]];
            }
            shortest[++k]=0;
            for(int j=k;j>0;j--){
                printf("%d->",shortest[j]);
            }
            printf("%d\n",shortest[0]);
        }
    }
    return 0;
}
SPFA算法思想： 
SPFA算法，就是队列优化的bellman-ford,是根据“每个顶点的最短路径不会更新次数太多”的特点来优化的。SPFA算法可以在O（km）的时间里求出源点到其他顶点的最短路，并且可以处理负权值。k我每个顶点入队列的平均次数，通常情况k为2左右。 
dis[i]存v0到i的距离，path[i]存i的“父顶点”。初始时dis[vo]=0,其他为INF，path[i]都为v0.并且v0入队列。 （与dijkstra的区别是SPFA是用队列而非优先队列，故可重复入队）
（1）取出队首的顶点u,扫描所有从u发出的边< u,v > ， 如果dis[v]>dis[u]+w(u,v);则更新，并且如果v不在队列里面则将v入队列。 （2）执行1直到队列为空。
例：给出n个顶点间的m条边，求出从原点0到其他顶点的所有最小权值，输出相应路径。 
 
输入： 
7 10 
0 1 6 
0 2 5 
0 3 5 
1 4 -1 
2 1 -2 

2 4 1 
3 2 -2 
3 5 -1 
4 6 3 
5 6 3

输出： 
1: 1 0->3->2->1 
2: 3 0->3->2 
3: 5 0->3 
4: 0 0->3->2->1->4 
5: 4 0->3->5 
6: 3 0->3->2->1->4->6

相关阅读

最短路 SPFA 算法详解与模板

转载请注明出处https://blog.csdn.net/bestsort个人感觉看SPFA之前推荐先看最短路 Dijkstra 算法详解与模板因为只有脑中理解了Di