SPFA算法简介

        全名为shortest path faster algorithm(最短路径快速算法)算法复杂度是与边数成正比

实现思路：

1）对每个结点建立数组 dis和vis

2）距离初始化位INF

3)  dis[s]=0 vis[s]=0  s为起点

4)  while 循环 queue不为空 不断查找队头松弛结点（缩短路径）的结点，并将其入队push vis->true,队头查找完后出队（vis->false)

代码实现：

SPFA
int vis[100010];
int dis[100010];
struct node{
    int to;
    int val;
};
int n,m;
vector<node>a[1000010];
void SPFA(int s){
    for(int i=1;i<=n;i++){
        dis[i]=1000000;
    }
    queue<int> p;
    p.push(s);
    dis[s]=0;
    vis[s]=1;
    while (!p.empty()) {
        int u=p.front();
        p.pop();
        vis[u]=false;
        for(int i=0;i<a[u].size();i++){
            if(dis[a[u][i].to]>(dis[u]+a[u][i].val)){
                dis[a[u][i].to]=dis[u]+a[u][i].val;
                p.push(a[u][i].to);
                vis[a[u][i].to]=1;
            }
        }
    }
}