Bellman-ford算法详解

什么是Bellman-ford算法

贝尔曼-福特算法（Bellman-Ford）是由理查德·贝尔曼（Richard Bellman）和莱斯特·福特创立的，求解单源最短路径问题的一种算法。其优于Dijkstra的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高。但它也有特别的用处，一般用于实现通过m次迭代求出从起点到终点不超过m条边构成的最短路径。

Dijkstra算法不能解决带有负权边的问题，而Bellman-ford算法可以解决带有负权边的问题，是求解带负权边的单源最短路问题的经典算法。时间复杂度是O(nm)，核心思想是”松弛操作”。解决带负权边的单源最短路问题还有一个常用的算法是SPFA算法，SPFA算法的时间复杂度一般是O(m)，最坏是O(nm)。

总结一下就是Dijkstra算法可以解决不带负权边的问题，而对于带有负权边的问题，又有Bellman-ford算法和SPFA解决。

基本思路

首先n次迭代，每一次循环所有边。我们这里用a,b,w表示存在一条从a走到b的边，权重是w。这里存边方式有很多种，可以用邻接表，结构体等。遍历所有边的时候更新一下其他点的距离，和Dijkstra算法类似，用当前这个点更新和它相连的点距离起点的距离。我们这里用dist数组表示每个点到起点的距离，那么更新操作就是dist[b]=min(dist[b],dist[a]+w)，这样就可以更新和a相连的b点距离起点的距离，这个更新的过程就是”松弛操作”。忘了说的一点就是在循环所有边的时候，每一次循环要先把dist数组备份一下，防止串联，这个后面会说。循环n次之后对所有的边一定满足dist[b]>m>>k; for(int i=0;i>a>>b>>c; edg[i]={a,b,c}; } //这里不用0x3f3f3f3f是因为防止n号点被负权边更新 if(bellman_ford()>0x3f3f3f3f/2) cout