spfa算法 最短路

SPFA（Shortest Path Faster Algorithm）（队列优化）算法：

1.求单源最短路径。

2.判负环（在差分约束系统中会得以体现）。

3.在Bellman-ford算法的基础上加上一个队列优化，减少了冗余的松弛操作，是一种高效的最短路算法。

如求如下图到各顶点的最短路径，d[i]记录到顶点i的最短路，Q队列

过程如下：

1.初始化：

方一：用数组代替队列，二维数组存储点边信息

#include<stdio.h>
#include<string.h>
#define Max 9999
// d[i]到i点的最短路，Q相当于队列，flag判断点是否在队列里，num判断该点进队列的次数 
int m,n,f[Max][Max],d[Max],Q[Max],flag[Max],num[Max];

int SPFA(int root){
    int top=,i,k=,u,v;
    for(i=;i<=m;i++){//初始化d[] 
      d[i]=Max; 
    }
    d[root]=;
    Q[k++]=root;//源点入队列 
    flag[root]=;//标记
    num[root]=;
    while(top<k){
        u=Q[top];// 源点出队列
        flag[u]=;// 标记，之后可以再次入队列 
        for(v=;v<=m;v++){
            if(d[v]>d[u]+f[u][v]){//进行松弛操作，更新最短路 
                d[v]=d[u]+f[u][v];
                if(flag[v]==){//没在队列，进队列
                   num[v]++;
                   if(num[v]>n){
                    printf("存在负环");
                    return ; 
                   } 
                   Q[k++]=v;
                   flag[v]=;   
                } 
            }
        }
        top++;//查找队列里的下一个点 
    }
    return ;
}

int main(){
    int a,b,c,i,j;
    memset(flag,,sizeof(flag));
    memset(num,,sizeof(num));
    scanf("%d%d",&m,&n);
    for(i=;i<=m;i++){
        for(j=;j<=m;j++){
            f[i][j]=Max;
        } 
    }
    for(i=;i<=n;i++){//用二维数组存储两点之间的关系 
        scanf("%d%d%d",&a,&b,&c);
        f[a][b]=c;
    }
    if(SPFA()==){//假设以1为源点
        for(i=;i<=m;i++){
            printf("%d ",d[i]);
        }
    }  
} 
           

方二：正规邻接表存储：有路径输出

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define Max 9999

typedef struct Edge{//边结点 
    int v;//边尾结点 
    int w;//权重 
    struct Edge *next;//下一个边结点 
}Ed;

struct Node{//顶点结点 
    Ed *head,*rec;
}N[Max];

// d[i]到i点的最短路，Q相当于队列，flag判断点是否在队列里，num判断该点进队列的次数 
int m,n,d[Max],Q[Max],flag[Max],num[Max],pre[Max];
Ed e[Max];

void adde(int u,int v,int w){
    Ed *p;
    p=(Ed*)malloc(sizeof(Ed));//动态建立链表 
    p->v=v;
    p->w=w;
    p->next=NULL;
    if(N[u].head==NULL){
        N[u].head=p;//边p的头结点是u 
        N[u].rec=p;//p是与u头结点相连的最新建的一条边 
    }
    else{
        N[u].rec->next=p;//将新边p跟在上一条后面，边的头结点都是u 
        N[u].rec=p;
    }

}

int relax(int u,int v,int w){//松弛操作 
    if(d[v]>d[u]+w){
        d[v]=d[u]+w;
        pre[v]=u;
        return ;
    }
    return ;
}

int spfa(int root){// 核心法 
    int top=,i,end=;
    d[root]=;
    Ed *pp;
    Q[end++]=root;
    num[root]=;
    while(top<end){//若队列不为空，继续松弛 
        pp=N[Q[top]].head;
        flag[Q[top]]=; //出队 
        while(pp!=NULL){
            if(relax(Q[top],pp->v,pp->w)==&&flag[pp->v]==){//松弛成功，若pp->v不在队列,则加在队列 
                Q[end++]=pp->v;
                num[Q[end++]]++;
                if(num[Q[end++]]>n){//判负环 
                    printf("存在负环");return ; 
                }
                flag[pp->v]=;  
            }
            pp=pp->next;//指向以Q[top]为头节点的下一条边    
        }
        top++;
    }
    return ; 
}

void out(){//输出顶点，最短路，路径 
    int i,j;
    printf("顶点  最短路  路径\n",i,d[i],i);
    for(i=;i<=m;i++){
        printf("%d     %d       %d ",i,d[i],i);
        j=i;
        while(pre[j]!=-){
            printf("%d ",pre[j]);
            j=pre[j];
        }
        printf("\n");
    }   
}

int main(){
    int i,j,k,u,v,w;
    memset(flag,,sizeof(flag));
    memset(num,,sizeof(num));
    scanf("%d%d",&m,&n);
    for(i=;i<=m;i++){
        pre[i]=-;
        d[i]=Max;
        N[i].head=NULL;
    }
    for(i=;i<=n;i++){//建立邻接表  
        scanf("%d%d%d",&u,&v,&w);
        adde(u,v,w);
    }
    if(spfa()==){
        out();  
    }
} 
           

方三：链式向前星存储图，不用指针，达到相同效果

链式向前星http://blog.csdn.net/qq_30331643/article/details/68621435

#include<stdio.h>
#include<string.h>
#define Max 9999

typedef struct Edge{//边结点 
    int v;//边尾结点 
    int w;//权重 
    int nexte;//下条边 
}Ed;

// d[i]到i点的最短路，Q队列，flag点是否在队列里，num点进队列次数 
int m,n,head[Max],d[Max],Q[Max],flag[Max],num[Max],pre[Max],k=;
Ed e[Max];

//构造边结点 
void adde(int u,int v,int w){
    e[k].w=w;
    e[k].v=v;
    e[k].nexte=head[u];//指向同顶点的下一条边 
    head[u]=k++; 
}

int relax(int u,int v,int w){//松弛操作 
    if(d[v]>d[u]+w){
        d[v]=d[u]+w;
        pre[v]=u;
        return ;
    }
    return ;
}
int spfa(int root){
    int top=,end=,i,j,l;//第i条边 
    d[root]=;
    Q[end++]=root;
    flag[root]=;
    num[root]++;
    while(top<end){
        i=head[Q[top]];
        flag[Q[top]]=;//出队列 
        for(j=i;j!=-;j=e[j].nexte){
            if(relax(Q[top], e[j].v, e[j].w)==&&flag[e[j].v]==){
                Q[end++]=e[j].v;//入队
                num[e[j].v]++;
                if(num[e[j].v]>n){//判负环 
                    printf("存在负环");return ; 
                }
                flag[e[j].v]=;             
            }
        }
        top++;
    }
    return ;
}

void out(){//输出顶点，最短路，路径 
    int i,j;
    printf("顶点  最短路  路径\n",i,d[i],i);
    for(i=;i<=m;i++){
        printf("%d     %d       %d ",i,d[i],i);
        j=i;
        while(pre[j]!=-){
            printf("%d ",pre[j]);
            j=pre[j];
        }
        printf("\n");
    }   
}

int main(){
    int i,j,u,v,w;
    memset(flag,,sizeof(flag));
    memset(num,,sizeof(num));
    scanf("%d%d",&m,&n);
    for(i=;i<=m;i++){
        head[i]=-;
        pre[i]=-;
        d[i]=Max;
    }
    for(i=;i<=n;i++){//建立邻接表  
        scanf("%d%d%d",&u,&v,&w);
        adde(u,v,w);
    }
    if(spfa()==){
        out();  
    }
}