一、用途
1. Bellman Ford算法是解决拥有负权边最短路问题的方法之一。还有一种方法是SPFA算法。
2. 二者相比，SPFA算法在效率方面是优于Bellman Ford算法的。但在某些情况下，解决最短路问题只能使用Bellman Ford算法。
3. 时间复杂度：Bellman Ford算法 O（nm）（n是点的个数，m是边数）
SPFA 算法一般是 O（m），最差情况是O（nm）
4.
什么情况下只能用Bellman Ford算法而不能用SPFA？
当最短路限制边数的时候，只能使用Bellman Ford。
5.
为什么有负权边的时候不能用Dijkstra算法，而用Bellman Ford？
Dijkstra算法不能解决负权边是因为 Dijkstra要求每个点被确定后st[j] = true，dist[j]就是最短距离了，之后就不能再被更新了（一锤子买卖），而如果有负权边的话，那已经确定的点的dist[j]不一定是最短了。
二、算法思路和注意事项
1.算法模板
for(int i=0;i<n-1;i++)
{
memcpy(backup,dist,sizeof(dist));
for(int j=0;j<m;j++)
dist[b]=min(dist[b],backup[a]+w);
}先开始让dist[]数组初始化为正无穷，dist[1]=0。
遍历n-1次，每次遍历m条边，用每一条边去更新各点到源点的距离。
解释算法：
dist[b]=min(dist[b],backup[a]+w);这段代码什么意思？
这是三角不等式，目的是
更新一条有向边右端点的数值
。w指的是这条边的权重。a是左端点，b是右端点，取当前dist[b]，和前者dist[a]+w，二者的最小值。每一次遍历边的时候后都会更新当前最短路。
memcpy(backup,dist,sizeof(dist));目的是什么？
这段代码是拷贝dist数组里的数据，转移到backup数组。作为备用，目的是使dist数组更新时，不受串联的影响。为什么会导致串联？假设有1，2，3三个点，用1号点更新了2号点。如果不使用backup[]数组，更新3号点时，不会使用2号点的原始数据，而会使用2号点改变之后的数据，造成错误。
外层循环是什么意思？
有个小细节：外层循环1次，跟1号点相隔1条边的点的dist[]值将不是正无穷（会确立此时的最短路）
外层循环2次，跟1号点相隔2条边的点的dist[]值将不是正无穷（会确立此时的最短路）
外层循环n-1次，跟1号点相隔n-1条边的点的dist[]值将不是正无穷（会确立此时的最短路）
希望大家可以画一下，画一下就知道了。
会确立此时的最短路
这句话什么意思？
因为会有负权环这个东西的出现，会一直改变之后点的最小路径值。所以此时的最小值不代表是永远的最小值。
何为负权环？
如上图，存在一个环，这个环每经过一次路径值都会减少，为了得到最小路径，这个环会一直走下去，从而之后的点最短路径不会确定。
所以我们解释了为什么外层是遍历n-1次？
是因为总共就n个点，两点间最长的一条边顶多有n-1条边。外层循环n-1次，所有的点的最短路都可以确定。但这个最短路后续会不会变，要看是否有负权环，如果有，那这个最短路只是当前最短路，后续还会变化。如果没有负权环，当前的最短路就是最短路径。
三、例题
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n 号点，输出 impossible。
注意：图中可能 存在负权回路 。
输入格式
第一行包含三个整数 n,m,k。
接下来 m 行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
点的编号为 1∼n。
输出格式
输出一个整数，表示从 1 号点到 n 号点的最多经过 k 条边的最短距离。
如果不存在满足条件的路径，则输出 impossible。
数据范围
1≤n,k≤500,
1≤m≤10000,
1≤x,y≤n，
任意边长的绝对值不超过 10000。
输入样例：
3 3 1
1 2 1
2 3 1
1 3 3
输出样例：
3代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=510,M=10010;
struct Edge
{
int a,b,w;
}edge[M];
int dist[N],backup[N];
int n,m,k;
void bellman_ford()
{
memset(dist,0x3f,sizeof(dist));
dist[1]=0;
for(int i=0;i<k;i++)
{
memcpy(backup,dist,sizeof(dist));
for(int j=0;j<m;j++)
{
int a=edge[j].a,b=edge[j].b,w=edge[j].w;
dist[b]=min(dist[b],backup[a]+w);
}
}
}
int main()
{
cin>>n>>m>>k;
for(int i=0;i<m;i++)
{
int a,b,w;
cin>>a>>b>>w;
edge[i]={a,b,w};
}
bellman_ford();
if(dist[n]>=0x3f3f3f3f-5000000) cout<<"impossible"<<endl;
else cout<<dist[n]<<endl;
return 0;
}可能存在的疑问：
Q1：外层为什么循环k次？
A：题目中是求从 1 号点到 n 号点的最多经过 k 条边的最短距离。循环k次，就可以知道跟1号点相隔k条边的点的当前最短路。如果循环大于k次，可能由于负权边的存在导致n号点最短路径更新变小。
Q2：为什么dist[n]>=0x3f3f3f3f-5000000，不应该是dist[n]>=0x3f3f3f3f吗？
A：因为遍历边的时候会更新dist值，对于正无穷（0x3f3f3f3f）也会有更新，如果n号点前面一个点是正无穷，每次遍历边的时候（
dist[b]=min(dist[b],backup[a]+w);
)也会对dist[n]有所修改。因为外层遍历最多500次，边权绝对值不大于10000，所以，如果n号点和1号点没有联系的话，它的dist[n]起码>=0x3f3f3f3f-5000000。