首先讲邻接表的实现,以前一直遇到题目都是用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++; } }
其求最短路径还是相对比较快速的,最主要是比较好写,结合邻接表实现起来非常简单,相对于dijkstra 算法来说首先它能够求解给定的图存在负权边,而dijkstra 算法是不能求解的,所以SPFA就好用多了。
这是dijkstra 算法以及Floyd算法的讲解:http://blog.csdn.net/y990041769/article/details/8524903
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; }
顺便说一道相关题目,poj1511,这道题是给出一个有向图,求从1点出发的最短路径和回到一点的最短路之和,其实就是先从1一次SPFA,然后把图中边反向在从1进行一次SPFA,题目数据卡的很严,首先结果要用long long,然后初始化最大值一定要足够大,后台有很大的数据,卡了两次,这道题目也可是用dijkstra 算法+优先队列优化过了。好了,就这样吧,累了一天了。
题目代码附上:
#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; }