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();  
    }
}