yの最爱 -----SPFA —关于他已经死了

1、什么是spfa算法？

SPFA 算法是 Bellman-Ford算法 的队列优化算法的别称，通常用于求含负权边的单源最短路径，以及判负权环。SPFA一般情况复杂度是 O(m) 最坏情况下复杂度和朴素 Bellman-Ford 相同，为 O(nm)。

bellman-ford算法操作如下：
for n次
for 所有边 a,b,w (松弛操作)
dist[b] = min(dist[b],back[a] + w)

pfa算法对第二行中所有边进行松弛操作进行了优化，原因是在bellman—ford算法中，即使该点的最短距离尚未更新过，但还是需要用尚未更新过的值去更新其他点，由此可知，该操作是不必要的，我们只需要找到更新过的值去更新其他点即可。

2、spfa算法步骤

queue <– 1
while queue 不为空
(1) t <– 队头
queue.pop()
(2)用 t 更新所有出边 t –> b，权值为w
queue <– b (若该点被更新过，则拿该点更新其他点)
时间复杂度 一般：O(m) 最坏：O(nm)
n为点数，m为边数

3、spfa也能解决权值为正的图的最短距离问题，且一般情况下比Dijkstra算法还好

1] Dijkstra算法中的st数组保存的是当前确定了到源点距离最小的点，且一旦确定了最小那么就不可逆了(不可标记为true后改变为false)；SPFA算法中的st数组仅仅只是表示的当前发生过更新的点，且spfa中的st数组可逆(可以在标记为true之后又标记为false)。顺带一提的是BFS中的st数组记录的是当前已经被遍历过的点。
2] Dijkstra算法里使用的是优先队列保存的是当前未确定最小距离的点，目的是快速的取出当前到源点距离最小的点；SPFA算法中使用的是队列(你也可以使用别的数据结构),目的只是记录一下当前发生过更新的点。

3) Bellman_ford算法里最后return-1的判断条件写的是dist[n]>0x3f3f3f3f/2;而spfa算法写的是dist[n]==0x3f3f3f3f;其原因在于Bellman_ford算法会遍历所有的边，因此不管是不是和源点连通的边它都会得到更新；但是SPFA算法不一样，它相当于采用了BFS，因此遍历到的结点都是与源点连通的，因此如果你要求的n和源点不连通，它不会得到更新，还是保持的0x3f3f3f3f。

4) Bellman_ford算法可以存在负权回路，是因为其循环的次数是有限制的因此最终不会发生死循环；但是SPFA算法不可以，由于用了队列来存储，只要发生了更新就会不断的入队，因此假如有负权回路请你不要用SPFA否则会死循环。

5) SPFA算法是由Bellman_ford算法优化而来，在最坏的情况下时间复杂度和它一样即时间复杂度为 O(nm) ，假如题目时间允许可以直接用SPFA算法去解Dijkstra算法的题目。

6) 求负环一般使用SPFA算法，方法是用一个cnt数组记录每个点到源点的边数，一个点被更新一次就+1，一旦有点的边数达到了n那就证明存在了负环。

7)SPFA 在形式上和宽度优先搜索非常类似，不同的是宽度优先搜索中一个点出了队列就不可能重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本身被改进，于是再次用来改进其它的点，这样反复迭代下去

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
int d[N], e[N], h[N], ne[N], w[N], idx, n, m;
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

int spfa()
{
    memset(d, 0x3f, sizeof d);
    d[1] = 0;

    queue<int> q;
    q.push(1);
    st[1] = true;
    while(q.size())
    {
        int t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(d[j] > d[t] + w[i])
            {
                d[j] = d[t] + w[i];
                if(!st[j])
                {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }
    if(d[n] == 0x3f3f3f3f) return 0x3f3f3f3f;
    return d[n];

} 

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while(m --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }

    int t = spfa();
    if(t == 0x3f3f3f3f) puts("impossible");
    else printf("%d", t);
    return 0;
}

st数组的作用：

判断当前的点是否已经加入到队列当中了；已经加入队列的结点就不
需要反复的把该点加入到队列中了，就算此次还是会更新到源点的距离，
那只用更新一下数值而不用加入到队列当中。
即便不使用st数组最终也没有什么关系，但是使用的好处在于可以提升效率
。

dijkstra 一

普通版，时间复杂度O(n²)

数据范围

1≤n≤500,
1≤m≤1e5 ,
图中涉及边长均不超过10000。
适用于稠密图，正权边（稠密图边比较多，甚至是点数量的二次方， 用邻接矩阵存。稀疏图n和m差不多，用邻接表存）

步骤（贪心思路，局部最优至全局最优）

1.初始化dist[1] = 0,其余节点的dist为正无穷大
2.（每次）找到一个未被标记的，所有点中dist[j]最小的点，然后标记它。
3. 再次更新它能到达所有点的dist
4.重复上述步骤，直到所有点都被访问完（每一次只找到一个最小的点来更新）。

核心代码

const int N = 510;
int g[N][N], dist[N], n, m;
bool st[N];

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n; i ++)
    {
        int t = -1;//dijkstra 不存在负权边， 可以作为未更新初始状态

        for (int j = 1; j <= n; j ++)
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        st[t] = true;

        for (int j = 1; j <= n; j ++)
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}
{
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    while(m --)
    {
        int x, y, z;
        cin >> x >> y >> z;
        g[x][y] = min(g[x][y], z);
    }
    cout<<dijkstra();
}

dijkstra 二（堆优化版）

堆优化版，时间复杂度O(mlogn)

数据范围

1≤n,m≤1.5×105,
图中涉及边长均不小于 0，且不超过 10000。
数据保证：如果最短路存在，则最短路的长度不超过 109。
适用于稀疏图，正权边（n 和 m 差不多级别， 用邻接表存)

步骤 并不一定只能求1~n， 还可以求i-j的距离，只需要改的d[i] = 0就可以了
利用堆找到找到一个未被标记的，所有点中dist[j]最小的点，然后标记它
再次更新它能到达所有点的dist（同一个起点）
重复上述步骤，直到所有点都被访问完（每一次只找到一个最小的点来更新）

核心代码

typedef pair<int, int> PII;//first存到源点的距离，因为排序默认按照第一个排
void add(int a, int b, int c)
{
    e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx ++;
}
int dijkstra()
{
    memset(d, 0x3f, sizeof d);
    d[1] = 0;

    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});
    while(heap.size())
    {
        PII k = heap.top();
        heap.pop();
        int ver = k.second, distance = k.first;

        if(sta[ver]) continue;
        sta[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];//点
            if (d[j] > distance + w[i])
            {
                d[j] = distance + w[i];
                heap.push({d[j], j});
            }
        }
    }

    if(d[n] == 0x3f3f3f3f) return -1;
    return d[n];
}

带记录

#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
using namespace std;
const int N = 510;
int g[N][N], dist[N], n, m, T[N][N], pg[N], pt[N];
string A, B;
int st[N];
int d1, d2;
void dijkstra_t(int s, int e)
{
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    memset(pt, -1, sizeof pt);
    dist[s] = 0;

    for (int i = 0; i < n; i ++)
    {
        int t = -1;//dijkstra 不存在负权边， 可以作为未更新初始状态

        for (int j = 0; j < n; j ++)
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        st[t] = 1;

        for (int j = 0; j < n; j ++)   
             if(dist[j] > dist[t] +  T[t][j])
             {
                pt[j] = t;//path[j]记录d[j]暂时最短路径的最后一个中途节点min_num，表明d[j]最后一段从节点min_num到节点j
                dist[j] = dist[t] + T[t][j];
             }
    }
    d2= dist[e];
}
void dijkstra_g(int s, int e)
{
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    memset(pg, -1, sizeof pg);
    dist[s] = 0;

    for (int i = 0; i < n; i ++)
    {
        int t = -1;//dijkstra 不存在负权边， 可以作为未更新初始状态

        for (int j = 0; j < n; j ++)
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        st[t] = 1;

        for (int j = 0; j < n; j ++)   
             if(dist[j] > dist[t] +  g[t][j])
             {
                pg[j] = t;//path[j]记录d[j]暂时最短路径的最后一个中途节点min_num，表明d[j]最后一段从节点min_num到节点j
                dist[j] = dist[t] + g[t][j];
             }

    }
    d1 = dist[e];
}

void pr(int s,int e)
{
    stack<char> q;
    int p = e;
    while(pg[p] != -1)
    {
        q.push(p + '0');
        p = pg[p];
    } 
    q.push(p + '0');
    while(!q.empty())
    {
        A += q.top();
        if(q.size() != 1) A += " => ";
        q.pop();
    }
}
void prt(int s,int e)
{
    stack<char> q;
    int p = e;
    while(pt[p] != -1)
    {
        q.push(p + '0');
        p = pt[p];
    } 
    q.push(p + '0');
    while(!q.empty())
    {
        B += q.top();
        if(q.size() != 1) B += " => ";
        q.pop();
    }
}
int main()
{
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
     memset(T, 0x3f, sizeof T);
    while(m --)
    {
        int a, b, dan, w, t;
        cin >> a >> b >> dan >> w >> t;
      //防止有重复边，所以取最小值 
        g[a][b] = min(g[a][b] , w);
        T[a][b] = min(T[a][b] , t);

        if(dan == 0)
        {
            g[b][a] = min(g[b][a] , w);
            T[b][a] = min(T[b][a] , t);
        }

    }
    int s, e;
    cin >> s >> e;
    dijkstra_t(s, e);
    prt(s, e);
    dijkstra_g(s, e);
    pr(s, e);
    if(A != B)
    {
        printf("Time = %d: " , d2);
        cout<<B<<endl;
        printf("Distance = %d: " , d1);
        cout<<A;
    }
    else
    {
        printf("Time = %d; Distance = %d: " , d2, d1);
        cout<<A;
    }


    return 0;
}