一、BFS与SPFA的区别

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

在所有边权都相等的图中，我们要求起点到图中各个结点的最短距离时，使用BFS即可（代码简单）。用BFS从起点开始遍历，当一个结点a是第一次被遍历到时，那么用结点a到起点的最短距离就可以用其父结点到起点的最短距离得到，此时结点a的最短距离就被确定了（用st[a]标记），然后将结点a放入队列，以此用来更新a的子节点距离起点的最短距离。下面是BFS的模板：

queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);

while (q.size()){
    int u = q.front();
    q.pop(); 

    for (int i = h[u]; ~i; i = ne[i]){
        int j = e[i];
        if (!st[j]){
            st[j] = true; // 表示点j已经被遍历过，即最短路已经确定
            q.push(j);
        }
    }
}

二、各种最短路算法中bool型数组st[]起到的作用

1.BFS宽搜

用BFS从起点开始遍历，当一个结点a是第一次被遍历到时，那么用结点a到起点的最短距离就可以用其父结点到起点的最短距离得到，此时结点a的最短距离就被确定了（用st[a]标记），然后将结点a放入队列，以此用来更新a的子节点距离起点的最短距离。

2.Dijkstra算法（O(n^2) –> O(mlogn)）

在Dijkstra算法中，st[]数组记录图中每一个结点到起点的最短距离是否已经确定，在Dijkstra最短路算法中，会先找出st[i]值为false的并且距离起点距离最短的结点i，利用i结点距起点的距离更新i结点的子结点到起点的距离，然后将i结点的st[i]值赋值为true，表示其距离起点的最短距离已经确定，在以后的循环中不再使用i结点更新其余结点。

这时有人就会提出疑问了：“上述中的i结点的最短距离如果在更新st[i]=true之后，在以后的循环中又被其它的点更新了呢？这时候难道不用将dist[i]重新入堆吗？”

首先，如果堆中有多个不同的dist[i]，那么使得i结点st[i]值变为true的一定是最小的dist[i]（即i结点距离起点的最小距离），其它的dist[i]再出堆之后，由于其不是i的最短的距离，无权也根本没必要用去更新i子结点的最短距离。

其次，对于上述问题，前提我们已知一个客观事实————当st[j]=true时，表明j结点的最短路已经确定（该事实由贪心证明，目前记住即可），那么在后续循环中由于在更新各个子结点之前都有如下判断:

if(dist[j] > distance + w[i])
{
    dist[j] = distance + w[i];
    heap.push({dist[j], j});
}

因此既然已经有dist[j]是j结点这一客观事实，那么dist[j]一定是小于等于distance + w[i]的，所以当st[j] = true之后，是不会在后续循环中又被它其余的父结点更新其dist[j]值的。但有一点需要注意，可能出现dist[j] == distance + w[i]的情况，即最短路径不止一条。

3.SPFA算法（一般为O(m)，最坏为O(mn)）

在SPFA算法中，st[i]的值记录的是i结点是否放入到队列当中，在SPFA算法中，会进行while(queue.size())的循环，每轮循环都会拿出队头元素i，并将其st[i]值赋值为false，表示其已经不在队列当中，并用i结点距离起点的最短距离去更新它的子结点的最短距离，如果子结点最短距离成功被更新，并且其不在队列当中，那么就将该子结点放到队列当中，以便以后更新该子结点的子结点。

因此在SPFA算法中，某一结点的最短距离可能被多次更新。

三、各种最短路算法的特殊应用

1.Bellman-Ford算法(O(mn))

特别针对于“有边数限制”的最短路问题，该算法的第一层循环的迭代次数n，就是指各个结点经过不超过n条边的前提下，到起点的最短距离时多少。

2.SPFA可判断图中有无负环

3.BFS和Dijkstra算法可以统计最短路条数

SPFA也可以，不过比较麻烦些，但如果遇到图中有负权边，也不得不用SPFA