SPFA的两种优化方法——SLF和LLL

Content:

一、SLF(Small Label First) 优化二、LLL(Large Label Last) 优化三、SLF+LLL四、优化效果五、其余代码

一、SLF(Small Label First) 优化

优化思路：将原队列改成双端队列，对要加入队列的点 p，如果 dist[p] 小于队头元素 u 的 dist[u]，将其插入到队头，否则插入到队尾。

//SLF优化 void spfa_slf(int s,int t,GH *G)//起点s，终点t，图G { //节点编号从0开始 int n=G->vexnum;//节点个数 int *dist=new int[n];//距离数组 bool *visit=new bool[n];//访问标记数组 int *pre=new int[n];;//前驱 AR *p; //初始化 memset(dist,0x3f,n*sizeof(int)); memset(visit,0,n*sizeof(bool)); memset(pre,-1,n*sizeof(int)); deque<int>Q;//建立双端队列，并将起点入队 visit[s]=1; dist[s]=0; Q.push_back(s); //进行操作 while (!Q.empty()) { int cur=Q.front(); Q.pop_front(); visit[cur]=0;//出队节点取消标记 p=G->N[cur].next; while (p)//遍历出队节点的直接后继 { if (dist[p->index] > dist[cur] + (p->weight))//需要进行松弛操作 { dist[p->index]=dist[cur] + (p->weight); pre[p->index]=cur; if (!visit[p->index]) { visit[p->index]=1; if(!Q.empty() && dist[p->index] < dist[Q.front()])//根据dist[p->index]与dist[Q.front()]的大小关系，决定p->index插入到队头还是队尾 Q.push_front(p->index); else Q.push_back(p->index); } } p=p->next; } } if (dist[t] == INF) cout<<"两点不连通."<<endl; else//输出最短路径 { cout<<"存在长度为"<<dist[t]<<"的最短路径:"<<endl; int *path=new int[n];//存放路径 int top=-1; int q=t; while (q != -1)//将前驱入栈 { top++; path[top]=q; q=pre[q]; } for (; top > 0; top--) cout<<G->vexname[path[top]]<<"-->"; cout<<G->vexname[path[0]]<<endl; delete []path; } delete []dist; delete []visit; delete []pre; }

二、LLL(Large Label Last) 优化

优化思路：对每个要出队的队头元素 u，比较 dist[u] 和队列中点的 dist 的平均值，如果 dist[u] 更大，将其弹出放到队尾，然后取队首元素进行相同操作，直到队头元素的 dist 小于等于平均值。

//LLL优化 void spfa_lll(int s,int t,GH *G)//起点s，终点t，图G { //节点编号从0开始 int n=G->vexnum;//节点个数 int *dist=new int[n];//距离数组 bool *visit=new bool[n];//访问标记数组 int *pre=new int[n];//前驱数组 int num;//队列中点的个数 int sum;//队列中点的dist之和 AR *p; //初始化 memset(dist,0x3f,n*sizeof(int)); memset(visit,0,n*sizeof(bool)); memset(pre,-1,n*sizeof(int)); queue<int>Q;//建立队列，并将起点入队 visit[s]=1; dist[s]=0; Q.push(s); num=1; sum=dist[s]; while (!Q.empty()) { int cur = Q.front(); //LLL优化 while (num*dist[cur] > sum)//表示队首元素的dist高于平均值，将其放到队尾 { Q.pop(); Q.push(cur); cur = Q.front(); } Q.pop(); visit[cur] = 0;//出队，并取消标记 num--; sum -= dist[cur]; p=G->N[cur].next; while (p) { if (dist[p->index] > dist[cur] + (p->weight))//需要进行松弛操作 { dist[p->index]=dist[cur] + (p->weight); pre[p->index]=cur; if (!visit[p->index]) { visit[p->index]=1; Q.push(p->index);//直接入队 num++;//更新相关参数 sum+=dist[p->index]; } } p=p->next; } } if (dist[t] == INF) cout<<"两点不连通."<<endl; else//输出最短路径 { cout<<"存在长度为"<<dist[t]<<"的最短路径:"<<endl; int *path=new int[n];//存放路径 int top=-1; int q=t; while (q != -1)//将前驱入栈 { top++; path[top]=q; q=pre[q]; } for (; top > 0; top--) cout<<G->vexname[path[top]]<<"-->"; cout<<G->vexname[path[0]]<<endl; delete []path; } delete []dist; delete []visit; delete []pre; }

三、SLF+LLL

这两种优化方法并不相互干扰，故可同时使用，下附代码。

//SLF+LLL优化 void spfa_slf_lll(int s, int t, GH *G)//起点s，终点t，图G { //节点编号从0开始 int n=G->vexnum;//节点个数 int *dist=new int[n];//距离数组 bool *visit=new bool[n];//访问标记数组 int *pre=new int[n];//前驱数组 int num;//队列中点的个数 int sum;//队列中点的dist之和 AR *p; //初始化 memset(dist,0x3f,n*sizeof(int)); memset(visit,0,n*sizeof(bool)); memset(pre,-1,n*sizeof(int)); deque<int>Q;//建立双端队列，并将起点入队 visit[s]=1; dist[s]=0; Q.push_back(s); num=1; sum=dist[s]; while (!Q.empty()) { int cur=Q.front(); //LLL优化 while (num*dist[cur] > sum)//表示队首元素的dist高于平均值，将其放到队尾 { Q.pop_front(); Q.push_back(cur); cur=Q.front(); } Q.pop_front(); visit[cur]=0;//出队，并取消标记 num--; sum-=dist[cur]; //SLF优化 p=G->N[cur].next;//遍历出队节点的直接后继 while (p) { if (dist[p->index] > dist[cur] + (p->weight))//需要进行松弛操作 { dist[p->index]=dist[cur] + (p->weight); pre[p->index]=cur; if (!visit[p->index]) { visit[p->index]=1; if(!Q.empty() && dist[p->index]<dist[Q.front()])//根据dist[p->index]与dist[Q.front()]的大小关系，决定p->index插入到队头还是队尾 Q.push_front(p->index); else Q.push_back(p->index); num++;//更新相关参数 sum+=dist[p->index]; } } p=p->next; } } if (dist[t] == INF) cout<<"两点不连通."<<endl; else//输出最短路径 { cout<<"存在长度为"<<dist[t]<<"的最短路径:"<<endl; int *path=new int[n];//存放路径 int top=-1; int q=t; while (q != -1)//将前驱入栈 { top++; path[top]=q; q=pre[q]; } for (; top > 0; top--) cout<<G->vexname[path[top]]<<"-->"; cout<<G->vexname[path[0]]<<endl; delete []path; } delete []dist; delete []visit; delete []pre; }

四、优化效果

以洛谷上的题目 P3381【模板】最小费用最大流 为例比较优化结果。

1.没有进行优化的结果 2.SLF优化的结果 3.LLL优化的结果 4.SLF+LLL优化的结果

五、其余代码

#include<cstdio> #include<iostream> #include<fstream> #include<cstring> #include<queue> using namespace std; #define maxN 1000 #define INF 0x3f3f3f3f #pragma warning(disable:4996) typedef struct arc//弧 { int index;//指向节点编号 int weight;//边的权值 struct arc *next; }AR; typedef struct MyGraph//图(包含邻接矩阵和邻接表) { int type;//0表示无向图，1表示有向图 int arcnum,vexnum;//边的个数、顶点个数 char **vexname;//存放顶点名称的二维数组 AR *N;//表头数组 int **A;//邻接矩阵 }GH; int findvex(char *s,GH *G);//找到图G中名称为s的节点编号，并将其返回 void createGraph(GH *G);//创建图G void showGraph(GH *G);//以邻接表的形式显示图G void spfa(int s,int t,GH *G);//起点s，终点t，图G void spfa_slf(int s,int t,GH *G);//起点s，终点t，图G void spfa_lll(int s,int t,GH *G);//起点s，终点t，图G void spfa_slf_lll(int s, int t, GH *G);//起点s，终点t，图G int main(void) { int s,t; GH *G; G=new GH; createGraph(G); cout<<"图的邻接表形式:"<<endl; showGraph(G); cout<<"请输入起点和终点编号(空格间隔):"; cin>>s>>t; cout<<"\n===========================无优化的SPFA=========================="<<endl; spfa(s,t,G); cout<<"\n===========================SLF优化的SPFA========================="<<endl; spfa_slf(s,t,G); cout<<"\n===========================LLL优化的SPFA========================="<<endl; spfa_lll(s,t,G); cout<<"\n=========================SLF+LLL优化的SPFA======================="<<endl; spfa_slf_lll(s,t,G); delete G; return 0; } int findvex(char *s,GH *G)//找到图G中名称为s的节点编号，并将其返回 { for(int i=0;i<G->vexnum;i++) { if(strcmp(s,G->vexname[i])==0)//找到匹配节点 return i; } cout<<"该点不存在."<<endl; exit(-1); } void createGraph(GH *G)//创建图G { int i,j,n,edge; char filename[]="graph.txt";//存放图的数据文件 char str[10],str1[10]; fstream file; AR *p; file.open(filename,ios::in); if(!file) { cout<<"打开文件失败!"<<endl; exit(-1); } file>>(G->type)>>n;//读取图的类型和节点数量 G->arcnum=0; G->vexnum=n; //为动态数组分配空间 G->vexname=new char*[n]; G->N=new AR[n]; G->A=new int*[n]; //对头结点数组和邻接矩阵初始化 for (i = 0; i < n; i++) { G->N[i].next = NULL; G->A[i] = new int[n]; for (j = 0; j < n; j++) G->A[i][j]=INF; } //读取顶点名称 for(i=0;i<n;i++) { file>>str; G->vexname[i]=new char[strlen(str)]; strcpy(G->vexname[i],str); } //读取边 while(!file.eof()) { file>>str>>str1>>edge; i=findvex(str,G); j=findvex(str1,G); //邻接表 p=new AR; p->index=j; p->weight=edge; p->next=G->N[i].next; G->N[i].next=p; //邻接矩阵 G->A[i][j]=edge; G->arcnum++;//边的个数增加 if(G->type==0)//如果是无向图 { //邻接表 p=new AR; p->index=i; p->weight=edge; p->next=G->N[j].next; G->N[j].next=p; //邻接矩阵 G->A[j][i]=edge; } } file.close();//关闭文件 } void showGraph(GH *G)//以邻接表的形式显示图G { AR *p;//用于遍历 for (int i = 0; i < G->vexnum; i++) { cout<<G->vexname[i]; p=G->N[i].next; while (p) { if (G->type == 1) cout<<"-->"; else//无向图没有箭头 cout<<"--"; cout<<G->vexname[p->index]<<"("<<(p->weight)<<")"; p=p->next; } cout<<endl; } cout<<endl; } //无优化 void spfa(int s,int t,GH *G)//起点s，终点t，图G { //节点编号从0开始 int n=G->vexnum;//节点个数 int *dist=new int[n];//距离数组 bool *visit=new bool[n];//访问标记数组 int *pre=new int[n];;//前驱 AR *p; //初始化 memset(dist,0x3f,n*sizeof(int)); memset(visit,0,n*sizeof(bool)); memset(pre,-1,n*sizeof(int)); queue<int>Q;//建立队列，并将起点入队 visit[s]=1; dist[s]=0; Q.push(s); //进行操作 while (!Q.empty()) { int cur=Q.front(); Q.pop(); visit[cur]=0;//出队节点取消标记 p=G->N[cur].next; while (p)//遍历出队节点的直接后继 { if (dist[p->index] > dist[cur] + (p->weight))//需要进行松弛操作 { dist[p->index]=dist[cur] + (p->weight); pre[p->index]=cur;//更新前驱 if (!visit[p->index]) { visit[p->index]=1; Q.push(p->index); } } p=p->next; } } if (dist[t] == INF) cout<<"两点不连通."<<endl; else//输出最短路径 { cout<<"存在长度为"<<dist[t]<<"的最短路径:"<<endl; int *path=new int[n];//存放路径 int top=-1; int q=t; while (q != -1)//将前驱入栈 { top++; path[top]=q; q=pre[q]; } for (; top > 0; top--) cout<<G->vexname[path[top]]<<"-->"; cout<<G->vexname[path[0]]<<endl; delete []path; } delete []dist; delete []visit; delete []pre; }