(算法基础)Bellman-ford算法
适用情景
Bellman-ford算法一般运用在求最短路的问题当中，适用于求最短路问题的单源最短路的存在负权边的情况。
时间复杂度
时间复杂度为O(m＊n)，n表示有n个点，m表示有m条边。
算法解释
首先是循环（迭代）n次，当然实际情况也不一定要求是n次，也可以是k次。但是这里面的实际意义非常关键：如果说该算法循环k-1次，从1号点经过k-1条边能够到达的所有点你们的最短距离已经确定下来；如果说该算法循环k次，从1号点经过k条边能够到达的所有点你们的最短距离也已经确定下来........ （当然，这个最短距离并不是最优版，是在只经过<=k条边的情况下的最短距离）
在每一次循环里面，去遍历所有的边（也正是因为如此，所以说这个算法里面存边的方式可以很随意，因为我只需要保证所有的边都能够全部遍历到就可以，因此可以直接开一个结构体去存边就行）。
struct point //存边(a,b,c) 表示从点a指向点b，权重为c
{
int x;
int y;
int z;
}接上文，比如说对于每一条边a,b,c（表示从点a指向点b，权重为c），那么这时候就干这个操作：
dist[b]=min(dist[b],dist[a]+c) //先不考虑备份，大意先搞懂在刚开始创建dist数组的时候，默认所有的点到一号点的距离都是无穷大，当然一号点本身除外。
memset(dist,0x3f,sizeof(dist));
dist[1]=0;在进行每一次循环迭代的时候。需要进行一个备份操作，把dist数组先备份到backup数组里面，这主要是为了防止串联现象的发生。如图解：
没有开始循环的时候，dist[ 1 ]=0, dist [ 2 ]与dist[ 3 ]都是正无穷大。然后进行了一次循环/迭代，这时候由于2号点与3号点都是可以通过1号点只经过一条边就可以走到，因此二号点和三号点的最短路已经确定，它们的最短距离分别为1和3。然后我们根据这个算法，在每一次循环的时候去遍了所有的边（3条），每次都dist[ b ] = dist[ a ] + c ; 如果没有备份的话，会导致dist[ 3 ]最终变为2，虽然2确实是更加优化的最短距离，但是这个最短距离是在从1号点经过两条边的基础之上，而我现在只进行了一次循环，我所得到的是从1号点只经过1条边走到的所有点的在最短路中边数为1这个前提下的最短距离。
for (int i=0;i<k;i++)
{
memcpy(backup,dist,sizeof(dist));
for (int j=1;j<=m;j++)
{
dist[b]=backup[a]+c;
}
}最后万一如果说从1号点是走不到n号点的，这种情况该如何在循环结束后去判断呢？因为dist数组所有元素初始化都是无穷大0x3f3f3f3f，但这边有个小坑，不能直接等于这个数字去判断。因为我们知道每次循环的话都会去遍历所有的边，在这个过程当中如果说n号点与某一个点之间存在着负权边，那么会对这个无穷大的数字造成略微的缩小。因此要这样子
if (dist[n]>0x3f3f3f3f/2)
{
printf("impossible\n");
}
.........例题
来源：AcWing
853. 有边数限制的最短路 - AcWing题库
#include <stdio.h>
#include <string.h>
#define MIN(a,b) ((a)<(b)?(a):(b))
typedef struct point
{
int a;
int b;
int c;
}point;
int main()
{
int n,m,k,a,b,c=0;
scanf("%d %d %d",&n,&m,&k);
point arr[m+1];
int dist[n+1];
memset(dist,0x3f,sizeof(dist));
dist[1]=0;
int backup[n+1];
for (int i=1;i<=m;i++)
{
scanf("%d %d %d",&a,&b,&c);
arr[i].a=a;
arr[i].b=b;
arr[i].c=c;
}
for (int i=0;i<k;i++)
{
memcpy(backup,dist,sizeof(dist));
for (int j=1;j<=m;j++)
{
dist[arr[j].b]=MIN(dist[arr[j].b],backup[arr[j].a]+arr[j].c);
}
}
if (dist[n]>0x3f3f3f3f/2)
{
printf("impossible\n");
}
else
{
printf("%d\n",dist[n]);
}
return 0;
}