SPFA的两种优化SLF和LLL

记录一个菜逼的成长。。

记下SPFA的两种优化，大牛请无视

SPFA算法有两个优化算法 SLF 和 LLL：
SLF：Small Label First 策略，设要加入的节点是$j$，队首元素为$i$，若$dist(j)<dist(i)$，则将j插入队首，否则插入队尾。
LLL：Large Label Last 策略，设队首元素为$i$，每次弹出时进行判断，队列中所有dist值的平均值为x，若$dist(i)>x$则将$i$插入到队尾，查找下一元素，直到找到某一$i$使得$dist(i)<=x$，则将i出对进行松弛操作。

char str[maxn][maxn];
int vis[maxn][maxn],dis[maxn][maxn],n,m;
int ans[30],sum,cnt;
int dx[] = {-1,-1,0,1,1,1,0,-1},dy[] = {0,1,1,1,0,-1,-1,-1};
dequeq;
void spfa()
{while(!q.empty()){PII f = q.front();q.pop_front();//LLL优化if(dis[f.fi][f.se] * cnt > sum){q.push_back(f);continue;}sum -= dis[f.fi][f.se];cnt--;vis[f.fi][f.se] = 0;for( int i = 0; i < 8; i++ ){int nx = f.fi + dx[i],ny = f.se + dy[i];if(nx < 1 || nx > n || ny < 1 || ny > m)continue;int w = (str[nx][ny] != str[f.fi][f.se]);if(dis[nx][ny] > dis[f.fi][f.se] + w){dis[nx][ny] = dis[f.fi][f.se] + w;if(!vis[nx][ny]){vis[nx][ny] = 1;//SLF优化if(dis[nx][ny] < dis[q.front().fi][q.front().se]){q.push_front(mp(nx,ny));}else {q.push_back(mp(nx,ny));}sum += dis[nx][ny];cnt++;}}}}
}
void init()
{cl(dis,INF);cl(vis,0);cl(ans,INF);sum = cnt = 0;
}

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