求最短路是图论中最基础的算法，最短路算法挺多，本文介绍SPFA算法。 关于其他最短路算法，请看我另一篇博客最短路算法详解
链式前向星概念
简单的说，就是存储图的一个数据结构。它是按照边来存图，而邻接矩阵是按点来存图，故链式前向星又叫边集数组
为何用链式前向星
当图的边数不多，而节点数很多稠密图)的时候，如果我们仍然用邻接矩阵来存的话，内存占用可能会很大，而这种情况在ACM竞赛中又是很常见的，此时链式前向星就显得尤为重要。
链式前向星详解
主要涉及到两个数组，一个是head[MAXE]数组，另一个是edge[MAXE]数组：
// edge数组是一个边集数组，存放一条边的信息 // to --- 该条边的终点 // next --- 下一条要访问的边存的是edge数组的下标). // 即：访问完了edge[i]，下一条要访问的就是edge[edge[i].next]， // 如果next为0，表示now这个节点作为起点的边已经全部访问完.下一步:Q.front)) // w --- 该条边的权值 struct Node { int to,next,w; }; Node edge[MAXE]; // idx --- edge数组的下标 // head[i] --- 表示以i节点为起点的所有出边在edge数组中的起始存储位置为head[i]. // 如果head[i]为0，表示结点i没有出边) int idx,head[MAXV];
View Code
理解了这两个数组，那么链式前向星也就理解了。其实链式前向星主要还是理解head数组和edge数组中的next这两个东西是怎么相互作用的，简单的说，就是head数组指导next，next指导edge的下一个下标。即：head[i]存储的是节点i作为起始节点的出边在edge数组中的起始存储位置，next引导节点i的下一条出边在edge数组中的存储位置。
怎么实现图的存储的呢？
这张图看懂了，链式前向星也就搞懂了。
链式前向星代码实现
//Memory Time // 2556K 362MS // by : Snarl_jsb #include<algorithm> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<vector> #include<queue> #include<stack> #include<iomanip> #include<string> #include<climits> #include<cmath> #define MAXV 10010 #define MAXE 50010 #define LL long long using namespace std; int T,n,m,u,v,w; int now,home,goal; bool vis[MAXV]; LL dis[MAXV]; namespace Adj { // edge数组是一个边集数组，存放一条边的信息 // to --- 该条边的终点 // next --- 下一条要访问的边存的是edge数组的下标). // 即：访问完了edge[i]，下一条要访问的就是edge[edge[i].next]， // 如果next为0，表示now这个节点作为起点的边已经全部访问完.下一步:Q.front)) // w --- 该条边的权值 struct Node { int to,next,w; }; Node edge[MAXE]; // idx --- edge数组的下标 // head[i] --- 表示以i节点为起点的所有出边在edge数组中的起始存储位置为head[i].如果head[i]为0，表示结点i没有出边) int idx,head[MAXV]; // 初始化 void init) { idx=1; memsethead,0,sizeofhead)); } // 加边函数 void addEdgeint u,int v,int w) // 起点，终点，权值 { edge[idx].to=v; // 该边的终点 edge[idx].w=w; // 权值 edge[idx].next=head[u]; // 指向head[u]后，head[u]又指向了自己) head[u]=idx; // 以u结点为起点的边在edge数组中存储的下标 idx++; } } using namespace Adj; void visitint sta) { forint i=1;i<=n;i++) { vis[i]=0; dis[i]=LLONG_MAX; } // 起点进队 queue<int>Q; Q.pushsta); vis[sta]=1; dis[sta]=0; while!Q.empty)) { int now=Q.front); Q.pop); // 在spfa中这儿需要改为0，因为每个节点需要重复进队 vis[now]=1; //取出now结点在edge中的起始存储下标当i=0，即edge[i].next为0，说明以now节点为起始点的边全部访问完) forint i=head[now];i;i=edge[i].next) { int son=edge[i].to; printf"%d --> %d , weight = %d ",now,edge[i].to,edge[i].w); if!vis[son]) { Q.pushson); // 子节点未访问过 vis[son]=1; // 标记已访问 } } } } int main) { while1) { Adj::init); scanf"%d",&n); scanf"%d",&m); whilem--) // 输入m条边 { int s,e,w; // 起点 终点 权值 scanf"%d %d %d",&s,&e,&w); addEdges,e,w); //若是无向图，反过来再加一次 } int start_point; //访问的起点 scanf"%d",&start_point); visitstart_point); } return 0; }
View Code
spfa概念
SPFA算法是求单源最短路径的一种算法，在Bellman-ford算法的基础上加上一个队列优化，减少了冗余的松弛操作，是一种高效的最短路算法。
SPFA的运用和分析
运用：
求单源最短路；
判断负环某个点进队的次数超过了v次，则存在负环)
分析：
平均时间复杂度：OkE),k<=2
最差时间复杂度：OVE) 出题人可能设计卡spfa时间复杂度的数据)
SPFA代码实现
//Memory Time // 2556K 362MS // by : Snarl_jsb #include<algorithm> #include<cstdio> #inlude<cstring> #include<cstdlib> #include<iostream> #include<vector> #include<queue> #include<stack> #include<iomanip> #include<string> #include<climits> #include<cmath> #define MAXV 10010 #define MAXE 50010 #define LL long long using namespace std; int T,n,m,u,v,w; int now,home,goal; bool vis[MAXV]; LL dis[MAXV]; namespace Adj { // edge数组是一个边集数组，存放一条边的信息 // to --- 该条边的终点 // next --- 下一条要访问的边存的是edge数组的下标).即：访问完了edge[i]，下一条要访问的就是edge[edge[i].next]，如果next为0，表示now这个节点作为起点的边已经全部访问完.下一步:Q.front)) // w --- 该条边的权值 struct Node { int to,next,w; }; Node edge[MAXE]; // idx --- edge数组的下标 // head[i] --- 表示以i节点为起点的所有出边在edge数组中的起始存储位置为head[i].如果head[i]为0，表示结点i没有出边) int idx,head[MAXV]; // 初始化 void init) { idx=1; memsethead,0,sizeofhead)); } // 加边函数 void addEdgeint u,int v,int w) // 起点，终点，权值 { edge[idx].to=v; // 该边的终点 edge[idx].w=w; // 权值 edge[idx].next=head[u]; // 指向head[u]后，head[u]又指向了自己) head[u]=idx; // 以u结点为起点的边在edge数组中存储的下标 idx++; } } using namespace Adj; void visitint sta) { forint i=1;i<=n;i++) { vis[i]=0; dis[i]=LLONG_MAX; } // 起点进队 queue<int>Q; Q.pushsta); vis[sta]=1; dis[sta]=0; while!Q.empty)) { int now=Q.front); Q.pop); vis[now]=0; // 在spfa中这儿需要改为0，因为每个节点需要重复进队 forint i=head[now];i;i=edge[i].next) //取出now结点在edge中的起始存储下标当i=0，即edge[i].next为0，说明以now节点为起始点的边全部访问完) { int w=edge[i].w; int son=edge[i].to; printf"%d --> %d , weight = %d ",now,edge[i].to,edge[i].w); ifdis[now]+w<dis[son]) // 松弛操作 { dis[son]=dis[now]+w; if!vis[son]) { Q.pushson); // 子节点未访问过 vis[son]=1; // 标记已访问 } } } } puts"/*************************************** END ******************************************/"); forint i=1;i<=n;++i) { printf"%d --> %d shortest distance is %d ",sta,i,dis[i]); } } int main) { while1) { Adj::init); scanf"%d",&n); scanf"%d",&m); forint i=1;i<=m;++i) // 输入m条边 { int s,e,w; // 起点 终点 权值 scanf"%d %d %d",&s,&e,&w); addEdges,e,w); //若是无向图，反过来再加一次 } int start_point; //访问的起点 scanf"%d",&start_point); visitstart_point); } return 0; } /* 5 6 1 2 5 1 3 9 1 4 1 3 5 2 4 3 3 4 5 7 1 */
View Code