\(spfa\) 的优化都是基于 \(deque\) 的，我们通常使用 \(LLL\) 优化，代码简单，优化效果最好，详情可见参考这里，例题可以参考这里
1. \(LLL\) 优化（入队优化）
Large Label Last 优化：思路就是将 \(dist\) 更大的点放入队尾，将 \(dist\) 更小的点放入队头，优先使用 \(dist\) 更小的点进行松弛操作。
void spfa(int head)
{
memset(dist, 0x3f, sizeof dist);
memset(st, false, sizeof st);
dist[head] = 0;
deque<int> q;
q.push_front(head);
st[head] = true;
while(q.size())
{
int cur = q.front();
q.pop_front();
st[cur] = false;
for(int i = h[cur]; i != -1; i = ne[i])
{
int j = e[i];
if(dist[j] > dist[cur] + w[i])
{
dist[j] = dist[cur] + w[i];
if(!st[j])
{
/*============== LLL 优化 ==============*/
if(q.empty() || dist[j] > dist[q.front()])
q.push_back(j);
else q.push_front(j);
/*======================================*/
st[j] = true;
}
}
}
}
}
2. \(SLF\) 优化（出队优化）
Small Label First 优化：优先让 \(dist\) 更小的节点出队来进行松弛操作，不过这个“小”并不好把握，总不能遍历一遍队列找这个小的 \(dist\) 把。因此，这里的“小”是平均意义上的小，即小于等于队列中所有元素的平均值，因此我们要维护队列元素个数 \(cnt\) （不用q.size()，调用函数可能更慢）和队列中的元素和 \(sum\)，通过 while 来进行判断，不过由于优化逻辑中有个 while，其优化效果可能很玄？
void spfa(int head)
{
memset(dist, 0x3f, sizeof dist);
memset(st, false, sizeof st);
dist[head] = 0;
deque<int> q;
q.push_front(head);
st[head] = true;
/*================================*/
int sum = dist[head], cnt = 1;
/*================================*/
while(q.size())
{
int cur = q.front();
/*============================*/
while(dist[cur] * cnt > sum)
{
q.push_front();
q.push_back(cur);
cur = q.front();
}
/*============================*/
q.pop_front();
st[cur] = false;
/*============================*/
cnt -- , sum -= dist[cur];
/*============================*/
for(int i = h[cur]; i != -1; i = ne[i])
{
int j = e[i];
if(dist[j] > dist[cur] + w[i])
{
dist[j] = dist[cur] + w[i];
if(!st[j])
{
q.push_back(j);
/*============================*/
cnt ++ , sum += dist[j];
/*============================*/
st[j] = true;
}
}
}
}
}