核心介绍¶

Bellman Ford算法同样是处理单源最短路问题，相较于Dijkstra算法多了处理负权，判断负环的应用场景。

引理与原理¶

f[u]是最短路的最终答案，d[u]是最短路的当前估计。 1. 引理:如果s->….->…->u->v为一条s到v的最短路，且在对边(u,v)进行松弛操作之前有f[u] = d[u]，则必有：在对边(u,v)松弛之后f[v] = d[v]。 2. 因此，对于这条最短路，最理想的情况是按照顺序从s到v依次对边进行松弛即可。但我们一般不知道边的顺序，所以无法按照最理想的情况依次松弛。所以，我们只要确保前面已经达到最终答案，即f[u] = d[u]即可，对这条边松弛即可。

松弛：是对边松弛。例如有一个边是m->n,对这个边松弛，就是dist[n] = min(dist[n], dist[m] + w[m][n]).

基本过程¶

核心步骤¶

对于V个节点，E条边。我们进行V-1次循环，每次循环对所有边进行松弛，就可以得到最终答案。

1. 进行k次循环后，距离起始点start的最短路的边数小于等于k的节点得到确定
2. 进行k次循环后，距离起始点start的最短路的边数小于等于k的节点得到确定
3. 进行k次循环后，距离起始点start的最短路边数小于等于k的节点得到确定
4. 重要的事情说三遍，这句话就是这个算法的题眼。既然这个东西成立，那么，任意两个节点之间的变数最多是V-1，所以最多进行V-1次循环就可以得到答案。下来我们解释这句话为什么成立。

原理解释¶

我们见微知著，用最小的单元向上推 1. 假设有一条最短路是start->A->B->C,这句话表明，A到start的最短路，就是start直接走向A的这条边，B到start的最短路start走到A，再走到B的这条路，同理，C也是。 2. 进行第一次循环后，我们对所有的边进行了松弛，那就一定对edge(start,A)进行了松弛，由引理可以知道，A这个节点的最短路答案就已经确定了。 3. 进行第二次循环。我们还是对所有的边进行了松弛，但是不知道edge(start,A)和edge(A,B)谁先被松弛，但根本没有关系，我们在松弛edge(A,B)的时候，A已经被确定了，这是第一轮所保证的结果。所以就可以发现，这一轮进行后B一定达到最终答案。 4. 下一轮同理，我们一定会对edge(B,C)进行松弛，并且B的结果由上一轮保证。 5. 因此我们进行了3轮后，A,B,C的最短路都被确定了,他们所对应的最短路边数一次是1，2，3,符合我们说的 进行k次循环后，距离起始点start的最短路的边数小于等于k的节点得到确定。 6. 我们回顾一下，发现这本质上是引理的非理想情况，我们不知道边的松弛顺序，所以会进行众多冗余操作，在每一轮逐步向前推进一点，为下一轮做出一定保证。

代码模板¶

相比于Dijkstra算法，这个代码就更为暴力简单，进行V-1次循环，每次对所有边松弛即可。

for(int i = 0; i < V - 1; i++){
    for(int[]edge : edges){
        dist[to] = Math.min(dist[from] + w[from][to], dist[to]);
    }
}
时间复杂度也很简单，O(VE).

变形(加入backup数组)¶

首先，我们先引入串扰的概念。 1. 我们先用一个图来举例子。这个图节点是start->A->B->C->D-E.类似于单链表。我们进行第一次循环，如果对边的松弛顺序恰巧是edge(start, A),edge(A,B)...那我们只进行了1次循环，就得到了最终答案。 2. 产生这个的原因是，在本轮中，更新后的A的信息对edge(A,B)的松弛起到了作用，这个更新链条不断延伸。这个现象我们就叫做串扰。 3. 那有的题目是要限制最短路的边数，例如力扣787题。这种题所要求的是，进行k次循环后，有且仅有距离起始点start的最短路的边数小于等于k的节点得到确定。 4. 对于这种题，我们的解决办法是，加入backup数组，克隆上一轮的结果，让本轮更新产生的信息无法向下传递。代码实现为

for(int i = 0; i < V - 1; i++){
    int[] backup = dist.clone();
    for(int[]edge : edges){
        dist[to] = Math.min(backup[from] + w[from][to], dist[to]);
    }
}

队列优化的Bellman Ford(SPFA)¶

基本的Bellman Ford每一轮是对所有边进行了松弛，我们可以对这个过程进行优化，省去一些根本不需要松弛的边。 1. 例如对edge(A,B)进行松弛,dist[B] = min(dist[B],dist[A] + w[A][B]),那如果dist[A]在上一轮或者这一轮的前面未被更新，那么这条边就根本不需要松弛。 2. 因此，我们引入一个队列，队列的元素代表被更新的点，这些点可以作为源去更新其他点。对队列元素的处理：将其引起的边松弛，加入由他引起的被更新的点，出队。一个元素不在入队，意味着没人再去更新他，即就是达到最终结果。当整个队为空，就得到了所有节点的最终答案。时间复杂度O(kE),最坏退化至O(VE).

boolean[] inQueue = new boolean[V + 1];
queue.offer(start);
inQueue[start] = true;
while( ! queue.isEmpty()){
    int u = queue.poll();
    inQueue[u] = false;
    //遍历u的所有邻居，将可更新的点更新，且入队。
    for(edge : graph.get(u)){
        if(dist[u] + w[u][v] < dist[v]){
            dist[v] = dist[u] + w[u][v];
            if(!inQueue[v]){
                queue.offer(v);
                inQueue[v] = true;
            }
        }
    }
}

处理负环¶

负环指的是从1个节点可以绕回来，并且绕回来的路径和为负值。 1. 判断方法：做完V-1轮循环后，再做一轮，松弛所有边，如果有节点被更新，那么存在负环。 2. 原因解释：如果再做一轮，仍然可以被更新，意味着存在一条长度优于当前答案的路径，且这条路径至少经过V条边。根据抽屉原理，这条路径必然经过某个点两次。即包含环。故这就是判断负环的方法。