邻接表实现单源最短路径SPFA算法 poj1511

我会带着你远行 2022-09-20 12:42 122阅读 0赞

**首先讲邻接表的实现，以前一直遇到题目都是用vector模拟，今天遇到一个题目vector超时，于是学习了用数组模拟实现邻接表，新学的数据结构，搞的不是很透彻，记录一下。**

**其实就是头插法，首先用一个结构体E记录节点的信息，指向那个节点，以及指向节点的权值等信息，给E结构体设置一个next，让它指向H数组，H数组初始化为-1，初始化为-1是为了方便判断某个点直接相连点是否找完了，自己还不是很透彻了，等搞透彻了详细解释，先把实现放在这里方便以后参考，当然H也可以写成结构体形式，写成数组较简单。**

int H[N];  //存头节点
    struct   //记录节点信息
    {
        int v;
        int count;
        int next;
    }E[N];
    int T,n,m,top;
    void Readmap(int m)  //读图
    {
        memset(H,-1,sizeof(H));
        int top=0;
        for(int i=0;i<m;i++){
            scanf("%d%d%d",&x[i],&y[i],&c[i]);
            E[top].v=y[i];E[top].count=c[i];
            E[top].next=H[x[i]];
            H[x[i]]=top++;
        }
    }

讲完了邻接表的实现就可以实现SPFA算法了， 算法的全称是：Shortest Path Faster Algorithm。

**其求最短路径还是相对比较快速的，最主要是比较好写，结合邻接表实现起来非常简单，相对于dijkstra 算法来说首先它能够求解给定的图存在负权边，而dijkstra 算法是不能求解的，所以SPFA就好用多了。**

**这是dijkstra 算法以及Floyd算法的讲解：[http://blog.csdn.net/y990041769/article/details/8524903][http_blog.csdn.net_y990041769_article_details_8524903]**

![Center][]![Image 1][]![Image 1][]**SPFA说白了就是一个不断更新的一个过程，官方说法叫松弛，比如说左边的图中，一个无向图，4个顶点的联通性以及各边的权值如图所示，要求从1点开始遍历所有点的最短路径，那么可以借助一个队列，首先顶一个数组sp初始化为无穷大，sp【1】=0，找和1直接相连的点，1--》2权值为1，比sp【2】的值大，松弛sp【2】=1，入队，找一下个与1直接相邻的，第一轮可以得到：**

**sp【2】=1； sp【3】=1； sp【4】=4；**

**，第一轮你松弛完毕，第二轮开始，从队列中出队元素，得到：**

**sp【4】=3，从1--》2--》4过来**

**sp【4】=2，从1--》3-->4过来**

**其他的点不满足松弛的条件，所以上面结果就是最优的，那么从1开始的最短路就是sp【1--》4】的值得和 0 + 1 + 1 + 2 = 4.**

**这就是一个SPFA算法的求解过程，可以证明在一个无圈图中最多经过（n-1）轮操作可以得到最优结果，其中n是顶点的数目，今天一个队员一直搞不明白为什么是n-1次，其实就是一个图如果是一条直线，其他点都在这个直线上的话就要进行（n-1）松弛，其实实际上远远小于这个数目。**

**下面是代码实现模板。**

**首先是邻接表版：**

long long SPFA(int st)
    {
        for(int i=1;i<=n;i++)
            sp[i]=inf;
        sp[1]=0;
        queue<int> q;
        q.push(st);
        while(!q.empty())
        {
            int kai=q.front();q.pop();
            for(int i=H[kai];i!=-1;i=E[i].next)
            {
                if(sp[E[i].v]>E[i].count+sp[kai]){
                    sp[E[i].v]=E[i].count+sp[kai];
                    q.push(E[i].v);
                }
            }
        }
        long long ans=0;
        for(int i=1;i<=n;i++)
            ans+=sp[i];
        return ans;
    }

然后是邻接矩阵版本：其中used数组记录是否访问，pre数据记录路径、

void spfa(int s,int dis[])
    {
        int i,pre[N];
        bool used[N];
        queue<int> q;
        memset(used,0,sizeof(used));
        memset(pre,-1,sizeof(pre));
        for(i=0; i<N; i++)
            dis[i]=inf;
        dis[s]=0;
        used[s]=true;
        q.push(s);
        while(!q.empty())
        {
            int u=q.front();
            q.pop();
            used[u]=false;
            for(i=0; i<map[u].size(); i++)
            {
                Node p=map[u][i];
                if(dis[p.v]>dis[u]+p.len)
                {
                    dis[p.v]=dis[u]+p.len;
                    pre[p.v]=u;
                    if(!used[p.v])
                    {
                        used[p.v]=true;
                        q.push(p.v);
                    }
                }
            }
        }
    }

应用：

1）判环

假如一个路径中存在环路，可以用这个算法判环，具体方法是加一个cnt 数组，记录每个点松弛的次数，如果松弛次数大于n。则说明存在环路。

题目：http://acm.nyist.net/JudgeOnline/problem.php?pid=973

2）

求最短路径，方法上面讲过

poj1511，

顺便说一道相关题目，这道题是给出一个有向图，求从1点出发的最短路径和回到一点的最短路之和，其实就是先从1一次SPFA，然后把图中边反向在从1进行一次SPFA，题目数据卡的很严，首先结果要用long long，然后初始化最大值一定要足够大，后台有很大的数据，卡了两次，这道题目也可是用**dijkstra 算法+优先队列优化过了。好了，就这样吧，累了一天了。**

![Image 1][]

**题目代码附上：**

#include <iostream>
    #include <vector>
    #include <cstring>
    #include <cstdio>
    #include <queue>
    const int N = 1001000;
    #define inf 10000000000LL
    using namespace std;
    int x[N],y[N],c[N],sp[N];
    int H[N];  //存头节点
    struct   //记录节点信息
    {
        int v;
        int count;
        int next;
    }E[N];
    int T,n,m,top;
    void Readmap(int m)  //读图
    {
        memset(H,-1,sizeof(H));
        int top=0;
        for(int i=0;i<m;i++){
            scanf("%d%d%d",&x[i],&y[i],&c[i]);
            E[top].v=y[i];E[top].count=c[i];
            E[top].next=H[x[i]];
            H[x[i]]=top++;
        }
    }
    long long SPFA(int st)
    {
        for(int i=1;i<=n;i++)
            sp[i]=inf;
        sp[1]=0;
        queue<int> q;
        q.push(st);
        while(!q.empty())
        {
            int kai=q.front();q.pop();
            for(int i=H[kai];i!=-1;i=E[i].next)
            {
                if(sp[E[i].v]>E[i].count+sp[kai]){
                    sp[E[i].v]=E[i].count+sp[kai];
                    q.push(E[i].v);
                }
            }
        }
        long long ans=0;
        for(int i=1;i<=n;i++)
            ans+=sp[i];
        return ans;
    }
    int main()
    {
        scanf("%d",&T);
        while(T--)
        {
            long long ans=0;
            scanf("%d%d",&n,&m);
            Readmap(m);
            int u=1;
            ans+=SPFA(u);
            top=0;
            memset(E,0,sizeof(E));
            memset(H,-1,sizeof(H));
            for(int i=0;i<m;i++)
            {
                E[top].v=x[i];
                E[top].count=c[i];
                E[top].next=H[y[i]];
                H[y[i]]=top++;
            }
            ans+=SPFA(u);
            printf("%lld\n",ans);
        }
        return 0;
    }

3）求最长路。初始为0，往大松弛。

[http_blog.csdn.net_y990041769_article_details_8524903]: http://blog.csdn.net/y990041769/article/details/8524903
[Center]: https://img-blog.csdn.net/20140116205011718?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQveTk5MDA0MTc2OQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Image 1]: