單源最短路_spfa

SPFA

適用范圍：
　　給定的圖存在負(fù)權(quán)邊，這時(shí)類似Dijkstra等算法便沒(méi)有了用武之地，而B(niǎo)ellman-Ford算法的復(fù)雜度又過(guò)高，SPFA算法便派上用場(chǎng)了。 我們約定有向加權(quán)圖G不存在負(fù)權(quán)回路，即最短路徑一定存在。
　　期望的時(shí)間復(fù)雜度O(ke)， 其中k為所有頂點(diǎn)進(jìn)隊(duì)的平均次數(shù)，可以證明k一般小于等于2。

判斷有無(wú)負(fù)環(huán)：
　　如果某個(gè)點(diǎn)進(jìn)入隊(duì)列的次數(shù)超過(guò)N次則存在負(fù)環(huán)

算法偽代碼: 

 procedure Shortest-Path-Faster-Algorithm(G, s)
  1    for each vertex v ≠ s in V(G)
  2        d(v) := ∞
  3    d(s) := 0
  4    offer s into Q
  5    while Q is not empty
  6        u := poll Q
  7        for each edge (u, v) in E(G)
  8            if d(u) + w(u, v) < d(v) then
  9                d(v) := d(u) + w(u, v)
 10                if v is not in Q then
 11                    offer v into Q

P3371 【模板】單源最短路徑
題意:
求出起點(diǎn)到每個(gè)點(diǎn)的最短路徑

#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int MAXN=10010;
const int MAXE=500010;
const int INF=0x7fffffff;
struct Node
{
    int to,next,val;
};
Node edge[MAXE];
int cnt,head[MAXN];
int dis[MAXN],inque[MAXN];//判斷是否在隊(duì)列中
void addEdge(int u,int v,int val)
{
    edge[cnt].to=v;edge[cnt].val=val;
    edge[cnt].next=head[u];head[u]=cnt++;
}
void spfa_bfs(int st)
{
    memset(inque,0,sizeof(inque));
    dis[st]=0;
    queue<int> que;
    que.push(st);
    int u,v,i;
    while(!que.empty())
    {
        u=que.front();que.pop();
        inque[u]=0;
        for(i=head[u];i!=-1;i=edge[i].next)
        {
            v=edge[i].to;
            if(dis[v]>dis[u]+edge[i].val)
            {
                dis[v]=dis[u]+edge[i].val;
                if(!inque[v])
                {
                    que.push(v);
                    inque[v]=1;
                }
            }
        }
    }
}
int main()
{
    int n,m,st,u,v,val;
    scanf("%d%d%d",&n,&m,&st);
    fill(dis+1,dis+1+n,INF);
    memset(head,-1,sizeof(head));
    cnt=0;
    for(int i=0;i<m;i++)
    {
        scanf("%d%d%d",&u,&v,&val);
        addEdge(u,v,val);
    }
    spfa_bfs(st);
    bool start=true;
    for(int i=1;i<=n;i++)
    {
        if(!start) printf(" ");
        printf("%d",dis[i]);
        start=false;
    }
    printf("\n");
}

Wormholes
題意:
圖是連通的,判斷負(fù)環(huán)
題解:
任選一個(gè)起點(diǎn)進(jìn)行spfa

#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int MAXN=10010;
const int MAXE=500010;
const int INF=0x3f3f3f3f;
struct Node
{
    int to,next,val;
};
Node edge[MAXE];
int cnt,head[MAXN];
int dis[MAXN],inque[MAXN];
int queNum[MAXN];//入隊(duì)次數(shù)
void addEdge(int u,int v,int val)
{
    edge[cnt].to=v;edge[cnt].val=val;
    edge[cnt].next=head[u];head[u]=cnt++;
}
bool spfa_bfs(int st,int n)
{
    memset(inque,0,sizeof(inque));
    memset(dis,INF,sizeof(dis));
    memset(queNum,0,sizeof(queNum));
    dis[st]=0;
    queue<int> que;
    que.push(st);
    queNum[st]++;
    int u,v,i;
    while(!que.empty())
    {
        u=que.front();que.pop();
        inque[u]=0;
        for(i=head[u];i!=-1;i=edge[i].next)
        {
            v=edge[i].to;
            if(dis[v]>dis[u]+edge[i].val)
            {
                dis[v]=dis[u]+edge[i].val;
                if(!inque[v])
                {
                    que.push(v);
                    queNum[v]++;
                    if(queNum[v]>n) return true;//有負(fù)環(huán)
                    inque[v]=1;
                }
            }
        }
    }
    return false;
}
int main()
{
    int n,m,k,u,v,val,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&m,&k);
        memset(head,-1,sizeof(head));
        cnt=0;
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d",&u,&v,&val);
            addEdge(u,v,val);
            addEdge(v,u,val);
        }
        for(int i=0;i<k;i++)
        {
            scanf("%d%d%d",&u,&v,&val);
            addEdge(u,v,-val);
        }
        if(spfa_bfs(1,n)) printf("YES\n");
        else printf("NO\n");
    }
}

其實(shí),spfa可以寫(xiě)成DFS的形式,只不過(guò)是把隊(duì)列換成了棧!同時(shí),用bfs形式的spfa來(lái)判斷負(fù)環(huán)會(huì)很慢,因?yàn)閷?duì)于有負(fù)環(huán)的情況我們必須在某個(gè)點(diǎn)入隊(duì)n次后才能判斷出來(lái)，如果n很大,那會(huì)非常耗時(shí),而用DFS可以改善,因?yàn)镈FS不會(huì)重復(fù)將一個(gè)點(diǎn)入棧,而是將下一個(gè)點(diǎn)入棧

看一看判負(fù)環(huán)的方法:

  • 1、在spfa同時(shí)記錄當(dāng)前節(jié)點(diǎn)是否在棧中
  • 2、如果某節(jié)點(diǎn)可被當(dāng)前節(jié)點(diǎn)松弛
    • 該節(jié)點(diǎn)還在棧中，說(shuō)明松弛路徑出現(xiàn)環(huán)，退出
    • 否則以該節(jié)點(diǎn)為當(dāng)前點(diǎn)進(jìn)行深搜spfa操作

但是,如果明確知道圖中沒(méi)有負(fù)環(huán),只是求最短路徑,還是要用BFS的spfa,DFS棧太深跑得比較慢!

這里先給出spfa_dfs求最短路的代碼(其實(shí)已經(jīng)可以判負(fù)環(huán)了)
暢通工程續(xù)
題意:
給出起點(diǎn)終點(diǎn),求最短路

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN=10010;
const int MAXE=500010;
const int INF=0x7fffffff;
struct Node
{
    int to,next,val;
};
Node edge[MAXE];
int cnt,head[MAXN];
int dis[MAXN],instack[MAXN];//判斷是否在棧中
void addEdge(int u,int v,int val)
{
    edge[cnt].to=v;edge[cnt].val=val;
    edge[cnt].next=head[u];head[u]=cnt++;
}
bool spfa_dfs(int u)
{
    instack[u]=1;
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(dis[v]>dis[u]+edge[i].val)
        {
            dis[v]=dis[u]+edge[i].val;
            if(!instack[v])
            {
                if(spfa_dfs(v)) return true;//有負(fù)環(huán)
            }
            else return true;//有負(fù)環(huán)
        }
    }
    instack[u]=0;
    return false;
}
int main()
{
    int n,m,st,ed,u,v,val;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(head,-1,sizeof(head));
        cnt=0;
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d",&u,&v,&val);
            addEdge(u,v,val);
            addEdge(v,u,val);
        }
        fill(dis,dis+n,INF);
        memset(instack,0,sizeof(instack));
        scanf("%d%d",&st,&ed);
        dis[st]=0;
        spfa_dfs(st);
        if(dis[ed]==INF) printf("-1\n");
        else printf("%d\n",dis[ed]);
    }
}

Wormholes
題意:
圖是連通的,判斷負(fù)環(huán)
題解:
任選一個(gè)起點(diǎn)進(jìn)行spfa

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN=10010;
const int MAXE=500010;
const int INF=0x3f3f3f3f;
struct Node
{
    int to,next,val;
};
Node edge[MAXE];
int cnt,head[MAXN];
int dis[MAXN],inStack[MAXN];//判斷是否在棧中
void addEdge(int u,int v,int val)
{
    edge[cnt].to=v;edge[cnt].val=val;
    edge[cnt].next=head[u];head[u]=cnt++;
}
bool spfa_dfs(int u)
{
    inStack[u]=1;
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(dis[v]>dis[u]+edge[i].val)
        {
            dis[v]=dis[u]+edge[i].val;
            if(!inStack[v])
            {
                if(spfa_dfs(v)) return true;//有負(fù)環(huán)
            }
            else return true;//有負(fù)環(huán)
        }
    }
    inStack[u]=0;
    return false;
}
int main()
{
    int n,m,k,u,v,val,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&m,&k);
        memset(head,-1,sizeof(head));
        cnt=0;
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d",&u,&v,&val);
            addEdge(u,v,val);
            addEdge(v,u,val);
        }
        for(int i=0;i<k;i++)
        {
            scanf("%d%d%d",&u,&v,&val);
            addEdge(u,v,-val);
        }
        memset(inStack,0,sizeof(inStack));
        fill(dis+1,dis+1+n,INF);
        dis[1]=0;
        if(spfa_dfs(1)) printf("YES\n");
        else printf("NO\n");
    }
}

其實(shí),如果只是判斷負(fù)環(huán),而不要求求最短路徑,dfs的spfa還有一個(gè)優(yōu)化的地方!
首先,如果存在負(fù)環(huán),那么肯定有某條邊是負(fù)數(shù)的,如果我們一開(kāi)始就從負(fù)數(shù)邊進(jìn)行spfa_dfs的話,那么肯定很快可以找到這個(gè)負(fù)環(huán),而且一旦找到負(fù)環(huán)就退出,這樣子會(huì)快很多!

那么一開(kāi)始怎么找到負(fù)數(shù)邊呢??
　　我們先看spfa_dfs中,現(xiàn)在進(jìn)行第一次dfs拓展,要使得第一次選中負(fù)邊,假設(shè)我們把dis數(shù)組初始化為0,進(jìn)行拓展時(shí),dis[u]=0,dis[v]=0,要使得dis[v]>dis[u]+edge[i].val,那么邊必定是負(fù)的,然后就對(duì)負(fù)邊進(jìn)行擴(kuò)展了。
　　也就是說(shuō)，dis數(shù)組初始化為0。這樣處理后，第一次拓展只會(huì)拓展到與起點(diǎn)相連邊權(quán)為負(fù)的邊。
　　當(dāng)然，求判負(fù)環(huán)＋求最短路時(shí)不能這樣初始化dis數(shù)組,因?yàn)橛锌赡艽嬖跈?quán)重為負(fù)的路徑且不存在負(fù)環(huán),那么這樣的最短路是合理的,所以還是老老實(shí)實(shí)把dis數(shù)組初始化為∞。

P3385 【模板】負(fù)環(huán)
題意:
給一個(gè)圖,判斷是否有負(fù)環(huán)。注意,圖不一定是聯(lián)通的,所以要通過(guò)多次不同起點(diǎn)單源最短判負(fù)環(huán)。(spfa_bfs會(huì)超時(shí),spfa_dfs的dis數(shù)組不初始化為0也會(huì)超時(shí))

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN=200010;
const int MAXE=200010*2;
const int INF=0x3f3f3f3f;
struct Node
{
    int to,next,val;
};
Node edge[MAXE];
int cnt,head[MAXN];
int dis[MAXN],inStack[MAXN];//判斷是否在棧中
void addEdge(int u,int v,int val)
{
    edge[cnt].to=v;edge[cnt].val=val;
    edge[cnt].next=head[u];head[u]=cnt++;
}
bool spfa_dfs(int u)
{
    inStack[u]=1;
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(dis[v]>dis[u]+edge[i].val)
        {
            dis[v]=dis[u]+edge[i].val;
            if(!inStack[v])
            {
                if(spfa_dfs(v)) return true;//有負(fù)環(huán)
            }
            else return true;//有負(fù)環(huán)
        }
    }
    inStack[u]=0;
    return false;
}
int main()
{
    int n,m,u,v,val,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        memset(head,-1,sizeof(head));
        cnt=0;
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d",&u,&v,&val);
            addEdge(u,v,val);
            if(val>=0) addEdge(v,u,val);
        }
        memset(inStack,0,sizeof(inStack));
        memset(dis,0,sizeof(dis));
        bool flag=false;
        for(int i=1;i<=n;i++)
        {
            if(spfa_dfs(i))
            {
                flag=true;
                break;
            }
        }
        if(flag) printf("YE5\n");
        else printf("N0\n");
    }
}

另外,再給出一個(gè)用全局變量flag的dfs吧,其實(shí)和上面一樣的

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN=200010;
const int MAXE=200010*2;
const int INF=0x3f3f3f3f;
struct Node
{
    int to,next,val;
};
Node edge[MAXE];
int cnt,head[MAXN];
int dis[MAXN],inStack[MAXN];//判斷是否在棧中
void addEdge(int u,int v,int val)
{
    edge[cnt].to=v;edge[cnt].val=val;
    edge[cnt].next=head[u];head[u]=cnt++;
}
bool flag;
void spfa_dfs(int u)
{
    inStack[u]=1;
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(dis[v]>dis[u]+edge[i].val)
        {
            dis[v]=dis[u]+edge[i].val;
            if(!inStack[v])
            {
                spfa_dfs(v);
                if(flag) return;//有負(fù)環(huán)
            }
            else
            {
                flag=true;
                return;//有負(fù)環(huán)
            }
        }
    }
    inStack[u]=0;
}
int main()
{
    int n,m,u,v,val,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        memset(head,-1,sizeof(head));
        cnt=0;
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d",&u,&v,&val);
            addEdge(u,v,val);
            if(val>=0) addEdge(v,u,val);
        }
        memset(inStack,0,sizeof(inStack));
        memset(dis,0,sizeof(dis));
        flag=false;
        for(int i=1;i<=n;i++)
        {
            spfa_dfs(i);
            if(flag) break;
        }
        if(flag) printf("YE5\n");
        else printf("N0\n");
    }
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容