Bellman ford 算法
一句话算法：Bellman ford 对于没有负权回路的图，对每个点进行 n-1 轮的松弛操作
图的性质
- 为了解决含有负权边 的图 最短路径问题而提出的算法
- 不能处理有负权回路的图的最短路径问题
bellman_ford算法思想
bellman_ford算法的本质是一种DP算法,我们设: $dis^1[u]$,$dis^2[u]$,…,$dis^{n-1}[u]$
其中:
- $dist^1[u]$为从源点v到终点u的只经过一条边的最短路径长度,并有$dis^1[u]=Edge[v][u]$;
- $dist^2[u]$为从源点v到终点u最多经过两条边的到达终点U的最短路径长度;
- $dist^3[u]$为从源点v到终点u最多经过不构成负权值回路的三条边到达终点u的最短路径长度;
- ………
- $dist^{n-1}[u]$为从源点v到终点u最多经过不构成负权值回路的n-1条边到达终点u的最短路径长度;
算法的最终目的是计算出$dist^{n-1}[u]$,它就是源点v到点u的最短路径长度(任意两个点之间的最短路径经过的边最多不超过n-1个,n为图的顶点数)
上面的设计其时也就是DP中的子问题,我们知道DP中最重要的就是:
- 分解子问题
- 子问题之间的递推关系(子问题的解推出大问题的解,DP方程)
那么DP方程就是:
$$dist^k[u] = min{dist^{k-1}[u] ,min{dist^{k-1}[j]+Edge[j][u]} }$$
其中
$dist^{k-1}[u]$表示:从源点v经过不构成负权回路的k-1条边到达点u的最短路径
$min{dist^{k-1}[j]+Edge[j][u]}$表示:从源点v不经过k－1条边到达点j的最短路径 + 边
$dist^1[u]=Edge[v][u]$表示边界
推论优化
现在我们就可以根据上面的DP方程来写我们的代码了,相一想如果用二维数组来存图,
第一层循环是2->n 次循环,第一个是u:1->n次循环遍历每个点,第三次是j:1->n次循环判断某个点是不是u的邻点
伪代码如下:
int Edge[n][n];//用来存图
int n,e;//n个点,e条边
int path[n];//记录路径,path[i]点i在最短路径中的上一个节点
void bellman_ford(int v){//源点v
int i,k,u;
for(i=0;i<n;i++){//dis[]初始化
dis[i] = Edge[v][i];
if(i != v && dis[i] < MAX ) path[i] = v;
else path[i]=-1;
}
for(k=2;k<n;k++)//求dis^2[],dis^3[],....,dis^n-1[]
for(u=0;u<n;u++)//遍历每一个点
{
if(u != v) .// 不= 起点
{
if(i=0;i<n;i++){//遍历每一个点,判断是不是u的邻点
if(Edge[i][u]<MAX && dis[u] > dis[i]+Edge[i][u])
{
dis[u] = dis[i] +Edge[i][u];
path[u]=i;
}
}
}
}
}
如果这样写有三层for循环,复杂度$O(n^3)$这样太复杂了,代码长度太长,仔细想一想:第一层for 是用来确定循环的次数:n-1,这个不能改变。
下面两层循环的含意:一个点去新相邻的点,当能更新的时候。如果我们遍历每条边(因为边上的点正好相邻,不用去判断点的相邻关系了)去更新点,可以省很多代码,同样bellman_ford也可以用一个句简单的话来概括:
一句话算法：Bellman ford 对于没有负权回路的图，对每个点进行 n-1 轮的松弛操作
伪代码
--->G(V,E):V个点，E条边
for(int i=1;i<=V-1;i++)//进行v-1轮操作
for(j=1;j<=E;j++){ //对每个点进行松弛，如果遍历每个边的话，每个边上的两个点正好相连
if(d[u] > d[a]+w(u,a))
d[u]=d[a]+w(u,a);
}
Dijkstra 与 bellman_ford算法的区别
- Dijkstra算法在求解过程中,源点到集合s内各项点的最短路径一旦求出,则之后就不变了,修改的仅仅是源点到T集合的各顶点的最短路径长度
- bellman_ford算法在求解过程中,每次循环都要修改所有顶点的dist[],也就是说源点到各个顶点的最短路径一直到bellman_ford算法结束才确定下来
想一想
是不是每个点都要进行n-1轮操作(松弛)