2017-07-27  22:18:11

writer：pprp

SPFA算法实质与Bellman-Ford算法的实质一样，每次都要去更新最短路径的估计值。

优化：只有那些在前一遍松弛中改变了距离点的值的点，才可能引起他们邻接点的距离估计值的改变；

做法：使用队列来缩小搜索范围的；

首先要将个点距离估计值设为+无穷，并将起始点加入队列。如果通过队列中的点i到相邻点j的距离小于原来到点j的距离，

即d[j]>d[i]+w[i][j]则d[j] = d[i] + w[i][j];将j点加入队列。当队列为空的时候，才能说明一丘处从起始点到任一点的最短距离。              

为了防止同一个点多次出现在队列里，需要对该点做标记以确定带点是够存在于队列中；

注意点：仅当图不存在负权回路，SPFA才能正常工作；

判断负权回路方法有很多：

1. 记录每个节点的进队次数，超过n说明有负权；
2. 记录这个节点在路径所处位置ord[i],每次更新的时候ord[i] = dor[x]+1;超过n证明有负权

---

代码如下：

#include 
     
      #include 
      
       using namespace std;const int INF = 99999999;struct node{    int n;    int v;    node*next;    node()    {        n = 0;        next = NULL;    }}*e[1001];       //存放每一个点到别的点的边int d[1001];     //估计值bool c[1001];    //判断该顶点是否存在与队列中queue
       
         qu;  //队列int n,m;         //n是顶点数,m是边的数目void init(){    cin >> n >> m;    node*p;    int x,y,v;    for(int i = 1; i <= n; i++)    {        cin >> x >> y >> v;        p = new node();        p->n = y;        p->v = v;        if(e[x]==NULL)            e[x] = p;        else        {            p->next = e[x]->next;            e[x]->next = p;        }    }}void spfa(int x){    int i;    node*p;    qu.push(x);     //  将起始点加入队列    for(i = 1; i <= n; i++)        d[i] = INF;    d[x] = 0;    for(i =1; i<=(int)qu.size(); i++)    //读取队列    {        p = e[qu.front()];    //和qu相连的边        while(p!=NULL)        {            if(d[qu.front()]+p->v < d[p->n])            {                d[p->n] = d[qu.front()]+p->v; //更新距离                if(!c[p->n])          //如果p->n点没有在队列里                {                    c[p->n] = 1;                    qu.push(p->n);                }            }            p = p->next;        //下一个点        }        c[qu.front()]=0;   　　　　 qu.pop();     //该点出队    }    for(i=1; i<=n; i++)        cout <
        
         <<" ";    cout << endl;}int main(){    init();    spfa(1);    return 0;}
        
       
      
     

之后还要再看一下