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

首先讲邻接表的实现,以前一直遇到题目都是用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

邻接表实现 单源最短路径SPFA算法 poj1511邻接表实现 单源最短路径SPFA算法 poj1511邻接表实现 单源最短路径SPFA算法 poj1511SPFA说白了就是一个不断更新的一个过程,官方说法叫松弛,比如说左边的图中,一个无向图,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;
}

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

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

题目代码附上:

#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;
}


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

上一篇:POJ 3592 强连通缩点+spfa最长路


下一篇:影响云计算核心问题的七个要素