贝尔曼-福特算法

$$O \left (|V| |E|\right )$$

$$O (|V|)$$

贝尔曼-福特算法（Bellman–Ford algorithm），求解单源最短路径问题的一种算法，由理查德·贝尔曼和小莱斯特·伦道夫·福特创立。有时候这种算法也被称为贝尔曼-福特-摩尔算法（Bellman–Ford–Moore algorithm），因为爱德华·F·摩尔也为这个算法的发展做出了贡献。它的原理是对图进行$|V|-1$次松弛操作，得到所有可能的最短路径。其优于戴克斯特拉算法的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高，高达$O (|V| |E|)$。但算法可以进行若干种优化，提高了效率。

## 算法

<image>

贝尔曼-福特算法与戴克斯特拉算法类似，都以松弛操作为基础，即估计的最短路径值渐渐地被更加准确的值替代，直至得到最优解。在两个算法中，计算时每个边之间的估计距离值都比真实值大，并且被新找到路径的最小长度替代。然而，戴克斯特拉算法以贪心法选取未被处理的具有最小权值的节点，然后对其的出边进行松弛操作；而贝尔曼-福特算法简单地对所有边进行松弛操作，共$|V|-1$次，其中$|V|$是图的点的数量。在重复地计算中，已计算得到正确的距离的边的数量不断增加，直到所有边都计算得到了正确的路径。这样的策略使得贝尔曼-福特算法比戴克斯特拉算法适用于更多种类的输入。

贝尔曼-福特算法的最多运行$O(|V|\cdot|E|)$（大O符号）次，$|V|$和$|E|$分别是节点和边的数量）。

### 伪代码

```
BellmanFord(G, source):

    for each vertex v in G: \\初始化
        dist[v] = infinity
        parent[v] = null

    dist[source] = 0

    for i = 1 to |V| - 1:   \\遍历
        for each edge (u, v) with weight w:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                parent[v] = u

    for each edge (u, v) with weight w:
        if dist[u] + w < dist[v]:
            return "存在负权环" \\检查负权环

    return dist, parent
```

## 原理

### 循环

每次循环操作实际上是对相邻节点的访问，第$n$次循环操作保证了所有深度为n的路径最短。由于图的最短路径最长不会经过超过$|V|-1$条边，所以可知贝尔曼-福特算法所得为最短路径。

### 负边权操作

与戴克斯特拉算法不同的是，戴克斯特拉算法的基本操作“拓展”是在深度上寻路，而“松弛”操作则是在广度上寻路，这就确定了贝尔曼-福特算法可以对负边进行操作而不会影响结果。

### 负权环判定

因为负权环可以无限制的降低总花费，所以如果发现第$n$次操作仍可降低花销，就一定存在负权环。

## 寻找负回路

当使用这个算法寻找最短路径时，有负回路会使算法找不到正确的答案。但是，由于在找到负回路后会中止算法，所以可以被用来寻找目标，例如在网络流分析中的消圈算法(Cycle Cancellation Algorithms)

## 优化

### 循环的提前跳出

在实际操作中，贝尔曼-福特算法经常会在未达到$|V| - 1$次前就出解，$|V| - 1$其实是最大值。于是可以在循环中设置判定，在某次循环不再进行松弛时，直接退出循环，进行负权环判定。

### 队列优化

西南交通大学的段凡丁于1994年提出了用队列来优化的算法。松弛操作必定只会发生在最短路径前导节点松弛成功过的节点上，用一个队列记录松弛过的节点，可以避免了冗余计算。原文中提出该算法的复杂度为$O(k|E|)$，$k$是个比较小的系数，但该结论被证明不适于于所有情况。

Pascal语言示例

```pascal
Begin
  initialize-single-source(G,s);
  initialize-queue(Q);
  enqueue(Q,s);
  while not empty(Q) do 
    begin
      u:=dequeue(Q);
      for each v∈adj[u] do 
        begin
          tmp:=d[v];
          relax(u,v);
          if (tmp<>d[v]) and (not v in Q) then
            enqueue(Q,v);
        end;
    end;
End;
```

C++语言示例

```c++
int SPFA(int s) {
	std::queue<int> q;
	bool inq[maxn] = {false};
	for(int i = 1; i <= N; i++) dis[i] = 2147483647;
	dis[s] = 0;
	q.push(s); inq[s] = true;
	while(!q.empty()) {
		int x = q.front(); q.pop();
		inq[x] = false;
		for(int i = front[x]; i !=0 ; i = e[i].next) {
			int k = e[i].v;
			if(dis[k] > dis[x] + e[i].w) {
				dis[k] = dis[x] + e[i].w;
				if(!inq[k]) {
					inq[k] = true;
					q.push(k);
				}
			}
		}
	}
	for(int i =  1; i <= N; i++) std::cout << dis[i] << ' ';
	std::cout << std::endl;
	return 0;
}
```

## 样例

例：

$V=\{v_1,v_2,v_3,v_4\}, E=\{(v_1,v_2),(v_1,v_3),(v_2,v_4),(v_4,v_3)\}$，$weight(v_1,v_2)=-1,weight(v_1,v_3)=3,weight(v_2,v_4)=3,weight(v_4,v_3)=-1$。

运行如表： $D:\texttt{Dist}[v],P:\texttt{Pred}[v]$

点｜$v_1$｜$v_2$｜$v_3$｜$v_4$

$D/P$｜$D/P$｜$D/P$｜$D/P$

初始化｜$0/\texttt{null}$｜$\infty/\texttt{null}$｜$\infty/\texttt{null}$｜$\infty/\texttt{null}$

循环第一次｜$0/\texttt{null}$｜$-1/v_1$｜$3/v_1$｜$\infty/\texttt{null}$

循环第二次｜$0/\texttt{null}$｜$-1/v_1$｜$3/v_1$｜$2/v_2$

循环第三次｜$0/\texttt{null}$｜$-1/v_1$｜$1/v_4$｜$2/v_2$

## 基本资料

- 车辆类别：最短路径问题（针对带权有向图）
- data：图
- 时间：$O \left (|V| |E|\right )$
- 容积、占地面积：$O (|V|)$