1. 简介

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

2. 特点

Bellman-Ford 算法的时间复杂度为 O(V*E) ,和另外几种计算最短路径的算法相比，时间复杂度是比较高的（也就是说，这个方法容易超时）。

但是，Bellman-Ford 算法也有它特有的优点：它能解决负权边问题，以及它特别适合于解决从 s 点出发，经过不超过 k 条边的前提条件下，到达 t 的最短路径问题。（也就是说，别的算法可能更快，但是遇到这两种情况就哑火了）。

关于负边权问题，本文后面的内容会加以探讨。

3. 算法思想

假设，有一张图，我们用符号 G=(V,E) 表示，其中，V 表示这张图包含了哪些点，E 表示这张图包含了哪些变，V 是点的集合，E 是边的集合。有 n 个点，m 条边，那么 Bellman-Ford 算法的内容是：

1. 初始化 s 到各个点的距离。s 到 s 为 0 , s 到其它点的距离是无穷大。我们用 dis 数组来记录最短路径，dis[s] = 0, 数组内其它元素设置为很大很大的数。

2. 进行 n-1 轮松弛操作。（这里是双层循环，第一层循环是循环 n-1 次；第二层循环是边，循环 m 次，枚举每一条边）

松弛：如果从 s 点先走到 i 点，然后又刚好存在一条边是连接 i 点到 j 点的，那么： dis[j] = min(dis[j],dis[i]+边i-j的权) 。

#include<bits/stdc++.h>
using namespace std;
struct Edge //表示边的结构体
{
    int From; // 边的起点
    int To;  //边的终点
    int Value; // 边的权
}e[100];
int dis[20]; 
int main()
{
	cin>>n>>m;
	
	//输入 m 条边
	for(int i=1;i<=m;i++)
	    cin>>e[i].From>>e[i].To>>e[i].Value;
	
	cin>>s>>t;

	//初始化s点到各个点的距离 
	memset(dis,0x3f,sizeof(dis)); //memset是按byte来填值，int 由 4个 byte组成，所以每个数组元素会赋值为 0x3f3f3f3f， 0x 开头是16进制数的意思 
	dis[s] = 0;
	
	for(int i=1;i<n;i++) //有 n 个节点，循环 n-1 次
	{
	    for(int j=1;j<=m;j++) //有 m 条边，循环 m 次
	    {
	        if(dis[e[j].To] > dis[e[j].From]+e[j].Value)
	            dis[e[j].To] = dis[e[j].From]+e[j].Value;	
	    }
	}

	if(dis[t]!=0x3f3f3f3f) //表示到 t 是被松弛过了 
	    cout<<dis[t]; // dis[t] 为从 s 出发，走不超过 n-1 步，到达 t 的最短路径
	else //等于原来的值，表示s和t点并不联通 
	    cout<<"s和t不联通";


	return 0;
}

4. 深入思考 Bellman-Ford 算法

4.1 为什么第一轮循环是 n-1 次

从 s 点出发，到达 t 点，假设不走重复路线（兜圈圈），那么最多最多走 n-1 步就可以到达。这是我们学数据结构：树 时候积累下来的知识。我们想象一下，从 s 出发，每次走一步去到一个新的点（新点指之前没有走过的点），整整图只有 n 个点，其中 1 个是自己，所以，走 n-1 步肯定可以走到任何一个联通的点了。

上图，从点 1 到点 4 ，就要分 4 步走。在 Bellman-Ford 算法中就是每轮松弛 1 个点，要分 4 轮进行，循环 4 次。

实际上，很多时候，可以提前结束，因为每一轮虽然只是走多一步，但是，是从已经走过的点出发往外延伸的，如果之前已经到达了 5 个点，从这 5 个点能延伸出 3 个新的点（也可能是旧的点，但是 dis 数组被更新），再下一轮循环，则是可以从这 3 个点往外延伸，最终不需要 n-1 轮就能到达所有的点了，这个问题和 BFS 的思想是一样。

Bellman-Ford 算法的其中一个改进点就在这里，如果发现某一轮循环没有松弛到任何的一个点（没有更新 dis 数组），那么就可以退出循环了。

上图，从点 1 到点 7，不需要 6 次就可以完成全部的松弛。

for(int i=1;i<n;i++)
{
    bool flag=true
    for(int j=1;j<=m;j++)
        if(dis[e[j].To] > dis[e[j].From]+e[j].Value)
        {
            dis[e[j].To] = dis[e[j].From]+e[j].Value;
            flag = false;
        }
    if(flag) break; //本轮没有松弛操作，后面也不会有的了，可以跳出循环
}

4.2 串联问题

串联本身是物理电学里面的意思，意思电流先后流过 2 个电路。我们讲 Bellman-Ford 算法的时候，说的串联问题就是一轮循环有多次松弛，后面的松弛使用了本轮循环前面的松弛结果，这意味着这一轮的某一次松弛，可能用到了几条边。

串联问题不一定是个问题，只有当题目问经过不超过 k 条边的情况下，s 到 t 点的最短路径你才需要回避串联，如果题目都不关心一共走了多少条边，串联就是一个好事，会加快计算。

要避免串联问题发生，我们在做松弛操作的时候 dis[j] = min(dis[j],dis[i]+边i-j的权) ，就要区分赋值好左边的 dis 和右边的 dis 。赋值号左边是新一轮计算的结果，赋值号的右边是上一轮的计算结果，我们更新了新一轮的 dis 数组值之后，只能在下一轮循环（第一层循环）使用。

for(int i=1;i<n;i++)
{
    memcpy(backup,dis,sizeof(dis)); // 把 dis 数组备份到 bcakup 数组
    for(int j=1;j<=m;j++)
        if(dis[e[j].To] > backup[e[j].From]+e[j].Value)
            dis[e[j].To] = backup[e[j].From]+e[j].Value;
}

4.3 负边权问题

上图就是有存在负权边的情况，从 2 到 4，从 4 到 3，从 3 又重新回到 2，每走一圈，边权加起来 -3 ，也就是说，只要无休止的转这个圈圈，总路径的边权和会越来越小。

所以，如果题目不对步数加以限制，这个情况就不会有最短路径。但是，题目会问你不超过 k 步的情况下最短路径是多少。那只需要控制一轮循环的循环次数为 k 即可。

for(int i=1;i<=k;i++) // 循环 k 次，就是不超过 k 步的最少路径
{
    memcpy(backup,dis,sizeof(dis)); // 把 dis 数组备份到 bcakup 数组
    for(int j=1;j<=m;j++)
        if(dis[e[j].To] > backup[e[j].From]+e[j].Value)
            dis[e[j].To] = backup[e[j].From]+e[j].Value;
}

5. 补充说明

本身只是大概介绍了，Bellman-Ford 算法，并没有严格论证这个算法的正确性。其实要严谨的证明，还是要做更多的论述的，作为中小学信息学竞赛生，不一定要那么深入的去了解这个证明过程，但是，我们大致上能想明白这个理论的含义，在自己的脑海里能讲得通，就可以了。最关键的，是你们要能用得出来，所以，要把这个算法转化成代码，要记得下来。