Spfa

Terence · 2018-08-09 22:34:51 · 个人记录

spfa

其实很好理解，主要是用于单源最短路径，我主要用的是队列的写法，一是快，而是好理解，再加上链式前向星的优化，应该会很快的------废话就说到这，具体原理见下：

1. 初始化距离dis为无穷大（一般可以设为0x3f3f3f3f,这个一般不太会超范围）。然后标记所有点都未访问，即visit[i]=0;
2. 将源点s压入队列，并标记已访问;
3. 开始循环，而使用链式前向星会更方便，***核心，也就是松弛操作

   dis[edge[i].to]=edge[i].w+dis[u];

   最后的最后，别忘了标记该点已访问；

如果你对前向星不了解，那就赶快去补下，前向星很好用的

代码如下：

void spfa(int ss){
    for(int i=1;i<m;i++){
        dis[i]=((i==ss) ? 0 : inf);
        visit[i]=0;
    }
    q.push(ss);
    visit[ss]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        visit[u]=0;
        for(int i=head[u];i!=0;i=edge[i].next)
        {
            if(!visit[edge[i].to] && dis[edge[i].to]>edge[i].w+dis[u])
                {
                //  printf("%d ",dis[edge[i].to]);
                    dis[edge[i].to]=edge[i].w+dis[u];
                //  printf("%d %d %d ",dis[edge[i].to],edge[i].w,dis[u]);
                    if(!visit[edge[i].to])
                        {
                            visit[edge[i].to]=1;
                            q.push(edge[i].to);
                        }
                }
            printf("\n");
        }
    }
}

如果不懂的话，我用前向星模拟了一遍，再不理解就真没办法了：

 u    v     w
from end  weight
 1    2     5
 2    5     4
 3    1     2
 6    3     4       
 6    5     1
 5    4     7

cnt++;
edge[cnt].to=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt;

1;
edge[1].to=2;
edge[1].w=5;
edge[1].next=head[1];
head[1]=1;

2;
edge[2].to=5;
edge[2].w=4;
edge[2].next=head[2];
head[2]=2;

3;
edge[3].to=1;
edge[3].w=2;
edge[3].next=head[3];
head[3]=3;

4;
edge[4].to=3;
edge[4].w=4；
edge[4].next=head[6];
head[6]=4;

5;
edge[5].to=5;
edge[5].w=1;
edge[5].next=head[6];
head[6]=5;

6;
edge[6].to=4;
edge[6].w=7;
edge[6].next=head[5];
head[5]=6;

for(int i=head[u];i!=0;i=edge[i].next)

i=head[6]--->