# 「学习笔记」SPFA 算法的优化()-其他

## 「学习笔记」SPFA 算法的优化()

### 栈优化

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;
}
}
}
}
}


### DEsopo-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$$ 一般设为所有边权的和的开方，即 $$\sqrt{sum}$$。

$$W$$ 一般设为所有边权的和的开方，即 $$\sqrt{sum}$$。

————————

### 栈优化

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;
}
}
}
}
}


### DEsopo-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$$ 一般设为所有边权的和的开方，即 $$\sqrt{sum}$$。

$$W$$ 一般设为所有边权的和的开方，即 $$\sqrt{sum}$$。