与其说是 SPFA 算法的优化,倒不如说是 Bellman-Ford 算法的优化。
栈优化
将原本的 bfs 改为 dfs,在寻找负环时可能有着更高效的效率,但是最坏复杂度为指数级别。
void dfs_spfa(int u) {
if (fg) return;
vis[u] = true;
for(pil it : son[u]) {
int v = it.first;
ll w = it.second;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
if (vis[v] == true) {//如果这个点被访问过,就说明这是负环
fg = true;//打标记
return;
}
else dfs_spfa(v);
}
}
vis[u] = false;
}
SLF 优化
将 queue
换成 deque
,判断与队首元素的 dis
的大小,小的就放队首,大的就放队尾。
void spfa(int s) {
for(int i = 1; i <= n; ++ i) {
dis[i] = inf;
}
dis[s] = 0;
q.push_back(s);
f[s] = 1;
while (!q.empty()) {
int u = q.front();
q.pop_front();
f[u] = 0;
for (pii it : son[u]) {
int v = it.first;
int w = it.second;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
if (! f[v]) {
if (! q.empty() && dis[v] < dis[q.front()]) {
q.push_front(v);
}
else q.push_back(v);
f[v] = 1;
}
}
}
}
}
D´Esopo-Pape 优化
将 queue
换成 deque
,判断一个点是否入过队列,没入过就放到队尾,如果就放到队首。
void spfa(int s) {
for(int i = 1; i <= n; ++ i) {
dis[i] = inf;
}
dis[s] = 0;
q.push_back(s);
f[s] = 1;
vis[s] = 1; // 是否入过队
while (!q.empty()) {
int u = q.front();
q.pop_front();
f[u] = 0;
for (pii it : son[u]) {
int v = it.first;
int w = it.second;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
if (! f[v]) {
if (vis[v]) {
q.push_front(v);
}
else {
q.push_back(v);
vis[v] = 1;
}
f[v] = 1;
}
}
}
}
}
LLL 优化
将 queue
换成 deque
,每次将入队结点距离和队内距离平均值比较,如果更大则插入至队尾,否则插入队首。
void spfa() {
ll sum = 0;
for (int i = 1; i <= n; ++ i) {
dis[i] = inf;
}
dis[s] = 0;
q.push_back(s);
g[s] = 1;
sum += dis[s];
while (!q.empty()) {
int u = q.front();
q.pop_front();
vis[u] = false;
sum -= dis[s];
for (pli it : son[u]) {
if (dis[it.second] > dis[u] + it.first) {
dis[it.second] = dis[u] + it.first;
if (! vis[it.second]) {
if (q.empty() || dis[it.second] > sum / ((int)q.size())) {
q.push_back(it.second);
}
else {
q.push_front(it.second);
g[it.second] = 1;
}
vis[it.second] = true;
}
}
}
}
}
SLF 带容错优化
将 queue
换成 deque
,判断与队首元素的 dis
的大小,设定一个值 \(W\),如果比队首元素大超过 \(W\) 则放队尾。
\(W\) 一般设为所有边权的和的开方,即 \(\sqrt{sum}\)。
mcfx 优化
在第 \(\left[L, R\right]\) 次访问一个结点时,将其放入队首,否则放入队尾。通常取 \(L = 2, R = \sqrt{\left|V\right|}\)。文章来源:https://www.toymoban.com/news/detail-430595.html
SLF + swap 优化
每当队列改变时,如果队首距离大于队尾,则交换首尾。文章来源地址https://www.toymoban.com/news/detail-430595.html
到了这里,关于「学习笔记」SPFA 算法的优化的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!