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);elseQ.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

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！