spfa最短路径算法模板（C++版带注释）

spfa最短路径算法模板（C++版带注释）

  废话不多说，直接上代码，小白发文，有任何不足欢迎大佬们斧正~v(≧∇≦)ﾉ

SPFA算法简介 该算法是求单源最短路的一种算法，spfa和Dijkstra很像，但spfa可以处理带负权边的图（但是不能有负权环，即围成环的各边权值加起来不能为负，否则会死循环），基于spfa该思想可稍作改进判断是否有负环（用一个cnt数组记录每个点到源点的边数，一个点被更新一次就+1，一旦有点的边数达到了n那就证明存在了负环）
  以下是算法代码

//数组构造邻接表
int n;
int h[N], e[M], w[M], ne[M], idx;       
int q[N], dist[N];
bool st[N];

// 添加一条边a->b，边权为c
void add(int a, int b, int c)
{
    //e[idx]指的是编号为idx的边的去向为何处，h[a]存储的是从a出发的所有边的单链表表头
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void spfa()  // 求1号点到n号点的最短路距离
{
    int hh = 0, tt = 0;
    memset(dist, 0x3f, sizeof dist);	//0x3f代表最大值，最小值可用0xcf
    dist[1] = 0;
    q[tt ++ ] = 1;
    st[1] = true;

    while (hh != tt)		//while循环控制出队
    {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])		//for循环控制入队+更新
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])     // 如果队列中已存在j，则不需要将j重复插入
                {
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }
}

int main(){
	...			//需先通过add函数，采取邻接表的方式构造好图
	spfa();
}

 
路漫漫其修远兮，吾将上下而求索