1.算法思想：

队列优化，去掉一些无用的松弛操作，用队列来维护松弛造作的点。继承了Bellman-Ford算法的思想，但时间复杂度相对来说提高了很多。

与BFS的算法有一些类似，利用了STL队列。

2.注意：

虽然大多数情况spfa跑的比较快，但时间复杂度仍为（Onm），主要用应用于有负边权的情况（如果没有负边权，推荐使用Dijkstra算法）。利用了邻接表建图，数据结构的基础一定要掌握好，而且该算法很容易超时，被卡，必须要谨慎选择该算法。

3.算法分析：

1.用dis数组记录点到有向图的任意一点距离，初始化起点距离为0，其余点均为INF，起点入队。

2.判断该点是否存在。（未存在就入队，标记）

3.队首出队，并将该点标记为没有访问过，方便下次入队。

4.遍历以对首为起点的有向边（t,i）,如果dis[i]>dis[t]+w(t,i),则更新dis[i]。

5.如果i不在队列中，则入队标记，一直到循环为空。

4.核心代码：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int INF = 1000000000;
const int maxn = 1000;
int dis[maxn];//记录最小路径的数组
bool vis[maxn];//标记
struct node {
    int s1;//记录结点
    int side;//边权
};
vector<node>mp[maxn];//用vector建立邻接表
void Spfa(int s) {
    queue<int>v;
    vis[s] = 1; v.push(s); dis[s] = 0;
    while (!v.empty()) {
        int q = v.front();
        v.pop(); vis[q] = 0;
        for (int i = 0; i < mp[q].size(); i++) {
            if (dis[mp[q][i].s1] > dis[q] + mp[q][i].side) {
                dis[mp[q][i].s1] = dis[q] + mp[q][i].side;//更新最短路径。            
                if (!vis[mp[q][i].s1]) {//是在更新新的值条件里面判断，一定特别注意这点
                    v.push(mp[q][i].s1);
                    vis[mp[q][i].s1] = 1;//标记未标记过的点
                }
            }
        }
    }
}

 完美撒花！！！

5.例题：P3371 【模板】单源最短路径（弱化版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目背景：

本题测试数据为随机数据，在考试中可能会出现构造数据让SPFA不通过（但本题可以用SPFA过），如有需要请移步 P4779

题目描述：

如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

输入输出样例：

输入 ：

4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

输出 ：

0 2 4 3

 样例说明：

图片1到3和1到4的文字位置调换

 题目分析：建立一个有向图，输出s到第i个结点的最短距离。（无疑是套刚刚那个模板）

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 10001;
const long long INF = 2147483647;
int dis[maxn];//记录最小路径的数组
int vis[maxn];//标记
int n, m, s;
struct node {
    int s1;//记录结点
    int side;//边权
};
void init() {
    for (int i = 1; i <= n; i++) {
        dis[i] = INF;
        vis[i] = 0;
    }
}
vector<node>mp[maxn];//用vector建立邻接表
void Spfa(int s) {
    queue<int>v;   
    vis[s] = 1; v.push(s); dis[s] = 0;
    while (!v.empty()) {
        int q = v.front();
        v.pop(); vis[q] = 0;
        for (int i = 0; i < mp[q].size(); i++) {
            if (dis[mp[q][i].s1] > dis[q] + mp[q][i].side) {
                dis[mp[q][i].s1] = dis[q] + mp[q][i].side;//更新最短路径。
                if (vis[mp[q][i].s1]) {
                    continue;//如果已经标记，则继续下一次循环
                }
                v.push(mp[q][i].s1);
            }
            
        }
    }
}
int main()
{
    int x, y, r;
   
    cin >> n >> m >> s;
    init();
    while (m--) {
        node h;
        cin >> x >> y >> r;
        h.s1 = y;//因为该图为有向图，记录指向的结点
        h.side = r;//记录路径
        mp[x].push_back(h);
    }
    Spfa(s);
    for (int i = 1; i <= n; i++) {        
            cout << dis[i] << " ";
    }
} 

        于是我->

         AC了，那SPFA算法就到此结束了，总体来说注意细节，在数据较大时候谨慎使用，感谢您的观看，图的最小路径的基础讲解就到这里啦，之后会更一些图论的题目，有任何算法问题欢迎交流！