spfa算法

spfa算法（优化）

spfa算法通常用于求含负权边的单源最短路径，以及判负权环。

允许输入有重边（Dijkstra不可）

Code of improved spfa

据说有时单用slf好，lll对于某些题会t

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100005;
const int inf = 0x3f3f3f3f;

struct node///存放“边”
{
    int from, to, w, pre;
} a[N];

///n为点的个数，dis[i]表示从起点到点i目前最短路径
///tot为队列内元素个数，sum为队列内元素的dis[]之和
int head[N], cnt, dis[N], times[N], tot, sum, n;
bool vis[N];///vis[i]：0表示i不在队列里，1表示i在队列里

void init()///受n影响，应安排在n被赋值之后
{
    cnt = 0;
    for(int i = 0; i <= n; ++i)
        dis[i] = inf, times[i] = 0, vis[i] = 0, head[i] = -1;
    return ;
}

void add(int from, int to, int w)
{
    a[cnt].from = from;
    a[cnt].to = to;
    a[cnt].w = w;
    a[cnt].pre = head[from];
    head[from] = cnt;
    cnt++;
}

bool spfa(int start)
{
    deque<int> q;
    dis[start] = 0;///到自己的距离为0
    vis[start] = 1;
    q.push_front(start);
    tot = 1, sum = 0;
    while(q.size())
    {
        int first = q.front();
        q.pop_front();
        vis[first] = 0;
        tot--;
        sum -= dis[first];
        cout << "当前检测点 " << first << '\n';

        for(int i = head[first]; ~ i; i = a[i].pre)
        {
            int t = a[i].to;
            cout << "当前检测终点 " << t << '\n';
            cout << "从起点到此终点最短路径 " << dis[t] << '\n';
            cout << "经由当前检测点到此终点最短路径 " << dis[first] + a[i].w << '\n';

            ///若 “起点到终点t的距离” 大于 “起点经由first点到终点t的距离”
            if(dis[t] > dis[first] + a[i].w)
            {
                dis[t] = dis[first] + a[i].w;
                if(!vis[t])
                {
                    vis[t] = 1;         ///极值优化             ///平均值优化
                    if(q.empty() || dis[t] > dis[q.front()] || dis[t] * tot >= sum)
                        q.push_back(t);
                    else
                        q.push_front(t);
                    sum += dis[t];
                    tot++;
                    if(++times[t] > n)
                        return 0;
                }
            }
        }
    }
    return 1;
}

int main()
{
    n = 5;///5个点
    init();
    add(1, 2, 20);
    add(2, 3, 30);
    add(2, 4, 20);
    add(4, 5, 20);
    add(3, 5, 100);
    if(spfa(1))
        for(int i = 1; i <= 5; ++i)
            cout << i << ' ' << dis[i] << '\n';
    return 0;
}

优先队列slf优化

struct cmp
{
    bool operator()(int a, int b)
    {
        return dis[a] > dis[b];
    }
};

priority_queue<int, vector<int>, cmp>q;///优先队列的极值优化

关于spfa死了

spfa貌似不被人接受：SPFA 的受到怀疑和最终消亡，是 OI 界水平普遍提高、命题规范完善和出题人的使命感和责任心增强的最好见证。

如何看待 SPFA 算法已死这种说法？ https://www.zhihu.com/question/292283275/answer/484871888