Bellman_Ford算法证明

Bellman_Ford算法

在最短路径问题中,我们给定一个带权重的有向图 G = ( V , E ) G=(V,E) G=(V,E)和权重函数 w w w, w ( u , v ) w(u,v) w(u,v)返回 u → v u\to v u→v的边权。图中的一条路径 p = < v 0 , v 1 , ⋯   , v k > p=<v_0,v_1,\cdots,v_k> p=<v0​,v1​,⋯,vk​>的权重 w ( p ) w(p) w(p)是构成路径的边的边权之和:

w ( p ) = ∑ i = 1 k w ( v i − 1 , v i ) w(p)=\sum \limits _{i=1}^{k}w(v_{i-1},v_i) w(p)=i=1∑k​w(vi−1​,vi​)

定义从节点 u u u到节点 v v v的最短路径权重 δ ( u , v ) \delta (u,v) δ(u,v)如下:

特别地,设源点为 s s s,那么 δ ( s , s ) = 0 \delta(s,s)=0 δ(s,s)=0,这很明显,原地踏步嘛,自己到自己的最短距离就是0

Bellman_Ford算法证明

如何理解任何一条路径呢?

最短路径不是唯一的,有很多条最短路径,也就是说会有很多最短路径 p p p,但是最短路径上的权值之和是唯一的,也就是说最终的 δ ( u , v ) \delta(u,v) δ(u,v)是唯一的


最短路径的最优子结构

最短路径的最优子结构:最短路径的子路径也是最短路径。

性质: δ ( s , v ) = δ ( s , u ) + w ( u , v ) \delta(s,v)=\delta(s,u)+w(u,v) δ(s,v)=δ(s,u)+w(u,v)

证明如下:

Bellman_Ford算法证明


负权和负环

  • 负权:图中某些边的权值为负数
  • 负环:存在一个环,这个环中所有边权之和为负数

Bellman_Ford算法证明

为什么最短路径中不能存在负权环和正权环呢?

  • 不能存在负权环。如上图,我们想要求从 u u u到 v v v的最短距离,但是每次进入这个环,权值之和都会减少5,那么可以在这个环上无限转圈,每转一圈权值之和减少5,但是一直转圈,不知道啥时候能停止转圈,然后通过最后一条边到达重点 v v v。假设只转一圈就出去了,那么 δ ( u , v ) = 3 \delta(u,v)=3 δ(u,v)=3;假设转两圈就出去了,那么 δ ( u , v ) = − 2 \delta (u,v)=-2 δ(u,v)=−2, ⋯ \cdots ⋯,由于无限转圈圈,那么得到的最短距离不确定
  • 不能存在正权环。如上图,假设正权环权值为2,4,1。每次进入环中,权值之和都会增加7,假设只转一圈就出去了,那么 δ ( u , v ) = 15 \delta(u,v)=15 δ(u,v)=15;假设转两圈就出去了,那么 δ ( u , v ) = 22 \delta (u,v)=22 δ(u,v)=22,很明显,如果无限转圈,那么最短距离是单调递增的。但是,如果不走这个环,那么得到的是 δ ( u , v ) = 5 + 1 + 3 = 9 \delta(u,v)=5+1+3=9 δ(u,v)=5+1+3=9。也就是说,如果去掉回路上的边,可以产生一个具有相同起点和终点、权值更小的路径。即如果 p = < v 0 , v 1 , ⋯   , v k > p=<v_0,v_1,\cdots,v_k> p=<v0​,v1​,⋯,vk​>是一条路径,而 c = < v i , v i + 1 , ⋯   , v j , v j + 1 , v i > c=<v_i,v_{i+1},\cdots,v_j,v_{j+1},v_i> c=<vi​,vi+1​,⋯,vj​,vj+1​,vi​>是这条路径上的一个正权回路(那么 w ( c ) > 0 w(c)>0 w(c)>0)。如果去掉回路上的边后,得到路径 p ′ = < v 0 , v 1 , ⋯   , v i , v j + 1 , v j + 2 , ⋯   , v k > p'=<v_0,v_1,\cdots,v_i,v_{j+1},v_{j+2},\cdots,v_k> p′=<v0​,v1​,⋯,vi​,vj+1​,vj+2​,⋯,vk​>,那么 w ( p ) = w ( p ′ ) + w ( c ) w(p)=w(p')+w(c) w(p)=w(p′)+w(c),因此 w ( p ′ ) < w ( p ) w(p')<w(p) w(p′)<w(p),所以 p p p不可能是从 v 0 v_0 v0​到 v k v_k vk​的最短路径

松弛操作

对于图中的每一个顶点 v v v,都设置一个属性 d i s [ v ] dis[v] dis[v],用来描述从源点 s s s到 v v v的最短路径上权值的上界,称为最短路径估计。

  • d i s [ v ] dis[v] dis[v]也就是从起点 s s s到点 v v v的最短路径上的估计值
  • δ ( u , v ) \delta(u,v) δ(u,v)是从起点 s s s到点 v v v的真实的最短路径上权值的最优解
  • 其实也就是要想办法设置一种算法,使得最终有 d i v [ v ] = δ ( u , v ) div[v]=\delta(u,v) div[v]=δ(u,v),真正要求的就是 d i v [ v ] div[v] div[v], δ ( u , v ) \delta(u,v) δ(u,v)只是设想的最优解

Bellman_Ford算法证明

如何理解松弛后一定有 d i s [ v ] ≤ d i s [ u ] + w ( u , v ) dis[v]\leq dis[u]+w(u,v) dis[v]≤dis[u]+w(u,v)呢?

  • 对于a图,松弛前, d i s [ u ] = 5 , w ( u , v ) = 2 , d i s [ v ] = 9 dis[u]=5,w(u,v)=2,dis[v]=9 dis[u]=5,w(u,v)=2,dis[v]=9,由于 d i s [ u ] + w ( u , v ) < d i s [ v ] dis[u]+w(u,v)<dis[v] dis[u]+w(u,v)<dis[v],然后我们让它执行了这句 d i s [ v ] = d i s [ u ] + w ( u , v ) dis[v]=dis[u]+w(u,v) dis[v]=dis[u]+w(u,v)。因此松弛后,有 d i s [ v ] = d i s [ u ] + w ( u , v ) dis[v]=dis[u]+w(u,v) dis[v]=dis[u]+w(u,v)
  • 对于b图,松弛前, d i s [ u ] = 5 , w ( u , v ) = 2 , d i s [ v ] = 6 dis[u]=5,w(u,v)=2,dis[v]=6 dis[u]=5,w(u,v)=2,dis[v]=6,由于 d i s [ u ] + w ( u , v ) > d i s [ v ] dis[u]+w(u,v)>dis[v] dis[u]+w(u,v)>dis[v],那么啥也不做。因此松弛后,有 d i s [ v ] < d i s [ u ] + w ( u , v ) dis[v]<dis[u]+w(u,v) dis[v]<dis[u]+w(u,v)
  • 综上,经过松弛操作后,一定有 d i s [ v ] ≤ d i s [ u ] + w ( u , v ) dis[v]\leq dis[u]+w(u,v) dis[v]≤dis[u]+w(u,v)

相关性质

Bellman_Ford算法证明


路径松弛性质

如果路径 p = < v 0 , v 1 , ⋯   , v k > p=<v_0,v_1,\cdots,v_k> p=<v0​,v1​,⋯,vk​>是从源点 s = v 0 s=v_0 s=v0​到节点 v k v_k vk​的一条最短路径,并且我们对 p p p的边按照 v 0 → v 1 , v 1 → v 2 , ⋯   , v k − 1 → v k v_0\to v_1,v_1\to v_2,\cdots,v_{k-1}\to v_k v0​→v1​,v1​→v2​,⋯,vk−1​→vk​的顺序进行了松弛操作,那么一定有 d i s [ v k ] = δ ( s , v k ) dis[v_k]=\delta(s,v_k) dis[vk​]=δ(s,vk​),而且只要是有按这样的顺序进行松弛操作过,结论就一定成立。这个性质的保持并不受到其他松弛操作的影响,即使它们与p的边上的松弛操作混合在一起也是一样的。

证明如下:

这个证明有点像递推。若 d i s [ v i − 1 ] = δ ( s , v i − 1 ) dis[v_{i-1}]=\delta (s,v_{i-1}) dis[vi−1​]=δ(s,vi−1​),则对 v i − 1 → v i v_{i-1}\to v_i vi−1​→vi​进行松弛操作后,由上面的收敛性子可知,得到: d i s [ v i ] = δ ( s , v i ) dis[v_i]=\delta(s,v_i) dis[vi​]=δ(s,vi​),再由上界性质,一旦有 d i s [ v i ] = δ ( s , v i ) dis[v_i]=\delta(s,v_i) dis[vi​]=δ(s,vi​),那么以后其值都不会发生改变了,该式子以后恒成立。又因为 d i s [ s ] = δ ( s , s ) = 0 , v 0 = s dis[s]=\delta(s,s)=0,v_0=s dis[s]=δ(s,s)=0,v0​=s,所以得证

也就是说,我们可以通过:

  • 由 d i s [ v 0 ] = δ ( s , v 0 ) dis[v_0]=\delta(s,v_0) dis[v0​]=δ(s,v0​),通过收敛性质可知,对 s → v 0 s\to v_0 s→v0​松弛后,推出 d i s [ v 1 ] = δ ( s , v 1 ) dis[v_1]=\delta(s,v_1) dis[v1​]=δ(s,v1​),再由上界性质,其值之后都不会发生变化,该式子以后恒成立
  • 由 d i s [ v 1 ] = δ ( s , v 1 ) dis[v_1]=\delta(s,v_1) dis[v1​]=δ(s,v1​),通过收敛性质可知,对 v 1 → v 2 v_1\to v_2 v1​→v2​松弛后,推出 d i s [ v 2 ] = δ ( s , v 2 ) dis[v_2]=\delta(s,v_2) dis[v2​]=δ(s,v2​),再由上界性质,其值之后都不会发生变化,该式子以后恒成立
  • ⋯ \cdots ⋯
  • 由 d i s [ v k − 1 ] = δ ( s , v k − 1 ) dis[v_{k-1}]=\delta(s,v_{k-1}) dis[vk−1​]=δ(s,vk−1​),通过收敛性质可知,对 v k − 1 → v k v_{k-1}\to v_{k} vk−1​→vk​松弛后,推出 d i s [ v k ] = δ ( s , v k ) dis[v_k]=\delta(s,v_k) dis[vk​]=δ(s,vk​),再由上界性质,其值之后都不会发生变化,该式子以后恒成立

如何理解:这个性质的保持并不受到其他松弛操作的影响,即使它们与p的边上的松弛操作混合在一起也是一样的?

  • 假设 d i s [ v i − 1 ] = δ ( s , v i − 1 ) dis[v_{i-1}]=\delta(s,v_{i-1}) dis[vi−1​]=δ(s,vi−1​)
  • 假设松弛了不在路径 p p p上的某一条边 ( v t , v i ) (v_t,v_i) (vt​,vi​),由上界性质, d i s [ v i ] ≥ δ ( s , v i ) dis[v_i]\geq \delta(s,v_i) dis[vi​]≥δ(s,vi​)(为什么不是直接 d i s [ v i ] = δ ( s , v i ) dis[v_i]=\delta (s,v_i) dis[vi​]=δ(s,vi​)呢?这是因为边 ( v t , v i ) (v_t,v_i) (vt​,vi​)并不是最短路径 p p p上的一条边,所以松弛 ( v t , v i ) (v_t,v_i) (vt​,vi​)后, d i s [ v i ] dis[v_i] dis[vi​]不是直接等于 δ ( s , v i − 1 ) \delta (s,v_{i-1}) δ(s,vi−1​)
  • 然后松弛了最短路径 p p p上的某一条边 ( v i − 1 , v i ) (v_{i-1},v_i) (vi−1​,vi​),由于它是最短路径 p p p上的边,因此松弛过后,由松弛性质、收敛性质、上界性质可知, d i s [ v i ] = δ ( s , v i ) dis[v_i]=\delta (s,v_i) dis[vi​]=δ(s,vi​)

这表明了,如果路径 p = < v 0 , v 1 , ⋯   , v k > p=<v_0,v_1,\cdots,v_k> p=<v0​,v1​,⋯,vk​>是从源点 s = v 0 s=v_0 s=v0​到节点 v k v_k vk​的一条最短路径,并且我们对 p p p的边按照 v 0 → v 1 , v 1 → v 2 , ⋯   , v k − 1 → v k v_0\to v_1,v_1\to v_2,\cdots,v_{k-1}\to v_k v0​→v1​,v1​→v2​,⋯,vk−1​→vk​的顺序进行了松弛操作,不论我们在其中穿插了多少不在路径p上的其它边,例如按照如下顺序进行松弛操作:

  • 按照 v 0 → v 1 , v t 0 → v t 1 , v 1 → v 2 , ⋯   , v k − 1 → v k v_0\to v_1,v_{t_0}\to v_{t_1},v_1\to v_2,\cdots ,v_{k-1}\to v_k v0​→v1​,vt0​​→vt1​​,v1​→v2​,⋯,vk−1​→vk​,即插入了 v t 0 → v t 1 v_{t_0}\to v_{t1} vt0​​→vt1​,但只是在原来 p p p的顺序中插入,并没有打乱之前 v 0 → v 1 , v 1 → v 2 , ⋯   , v k − 1 → v k v_0\to v_1,v_1\to v_2,\cdots,v_{k-1}\to v_k v0​→v1​,v1​→v2​,⋯,vk−1​→vk​的顺序
  • 按照 v 1 → v 2 , v 0 → v 1 , v k − 1 → v k , v 1 → v 2 , ⋯   , v k − 1 → v k v_1\to v_2,v_0\to v_1,v_{k-1}\to v_{k},v_1\to v_2,\cdots ,v_{k-1}\to v_k v1​→v2​,v0​→v1​,vk−1​→vk​,v1​→v2​,⋯,vk−1​→vk​,即插入了 v 1 → v 2 v_1\to v_2 v1​→v2​和 v k − 1 → v k v_{k-1}\to v_k vk−1​→vk​,但只是在原来 p p p的顺序中插入,并没有打乱之前 v 0 → v 1 , v 1 → v 2 , ⋯   , v k − 1 → v k v_0\to v_1,v_1\to v_2,\cdots,v_{k-1}\to v_k v0​→v1​,v1​→v2​,⋯,vk−1​→vk​的顺序
  • 也就是说,不论你在 v 0 → v 1 , v 1 → v 2 , ⋯   , v k − 1 → v k v_0\to v_1,v_1\to v_2,\cdots,v_{k-1}\to v_k v0​→v1​,v1​→v2​,⋯,vk−1​→vk​这个顺序中,插入了多少条松弛边,最终的结果都是 d i s [ v k ] = δ ( s , v k ) dis[v_k]=\delta (s,v_k) dis[vk​]=δ(s,vk​)
  • 但是要注意,证明的前提是路径 p = < v 0 , v 1 , ⋯   , v k > p=<v_0,v_1,\cdots,v_k> p=<v0​,v1​,⋯,vk​>是从源点 s = v 0 s=v_0 s=v0​到节点 v k v_k vk​的一条最短路径

举个栗子解释上面的证明:

假设 p ( v 0 , v 1 , v 4 ) p(v_0,v_1,v_4) p(v0​,v1​,v4​)是 s = v 0 s=v_0 s=v0​到 v 4 v_4 v4​的最短路径,且 δ ( s , v 4 ) = − 3 \delta(s,v_4)=-3 δ(s,v4​)=−3,初始化dis数组为:

s=v0 v1 v2 v3 v4
0 INF INF INF INF

Bellman_Ford算法证明

  • 栗子一:假设我们按照 v 0 → v 1 , v 1 → v 4 , ⋯ v_0\to v_1,v_1\to v_4,\cdots v0​→v1​,v1​→v4​,⋯的顺序进行松弛操作,那么对 v 0 → v 1 v_0\to v_1 v0​→v1​松弛后, d i s [ v 0 ] + w ( u , v ) = 0 + 2 = 2 < d i s [ v 1 ] = ∞ dis[v_0]+w(u,v)=0+2=2<dis[v_1]=\infin dis[v0​]+w(u,v)=0+2=2<dis[v1​]=∞,所以松弛后, d i s [ v 1 ] dis[v_1] dis[v1​]被更新为2;接着对 v 1 → v 4 v_1\to v_4 v1​→v4​松弛后, d i s [ v 1 ] + w ( u , v ) = 2 + ( − 5 ) = − 3 < d i s [ v 4 ] = ∞ dis[v_1]+w(u,v)=2+(-5)=-3<dis[v_4]=\infin dis[v1​]+w(u,v)=2+(−5)=−3<dis[v4​]=∞,所以 d i s [ v 4 ] dis[v_4] dis[v4​]被更新为-3 ⋯ \cdots ⋯
  • 栗子二:假设我们按照 v 0 → v 1 , v 3 → v 4 , v 0 → v 2 , ⋯   , v 1 → v 4 v_0\to v_1,v_3\to v_4,v_0\to v_2,\cdots ,v_1\to v_4 v0​→v1​,v3​→v4​,v0​→v2​,⋯,v1​→v4​,在正确顺序中插入了 v 3 → v 4 , v 0 → v 2 v_3\to v_4,v_0\to v_2 v3​→v4​,v0​→v2​。那么对 v 0 → v 1 v_0\to v_1 v0​→v1​松弛后, d i s [ v 0 ] + w ( u , v ) = 0 + 2 = 2 < d i s [ v 1 ] = ∞ dis[v_0]+w(u,v)=0+2=2<dis[v_1]=\infin dis[v0​]+w(u,v)=0+2=2<dis[v1​]=∞,所以松弛后, d i s [ v 1 ] dis[v_1] dis[v1​]被更新为2;那么对 v 3 → v 4 v_3\to v_4 v3​→v4​松弛后, d i s [ v 3 ] + w ( u , v ) = ∞ + 2 = ∞ + 2 > d i s [ v 1 ] = ∞ dis[v_3]+w(u,v)=\infin+2=\infin+2>dis[v_1]=\infin dis[v3​]+w(u,v)=∞+2=∞+2>dis[v1​]=∞,所以松弛后, d i s [ v 4 ] dis[v_4] dis[v4​]没有被更新,仍然保持原来的值 ∞ \infin ∞;那么对 v 0 → v 2 v_0\to v_2 v0​→v2​松弛后, d i s [ v 0 ] + w ( u , v ) = 0 + 3 = 3 < d i s [ v 2 ] = ∞ dis[v_0]+w(u,v)=0+3=3<dis[v_2]=\infin dis[v0​]+w(u,v)=0+3=3<dis[v2​]=∞,所以松弛后, d i s [ v 2 ] dis[v_2] dis[v2​]被更新为2; ⋯ \cdots ⋯;接着对 v 1 → v 4 v_1\to v_4 v1​→v4​松弛后, d i s [ v 1 ] + w ( u , v ) = 2 + ( − 5 ) = − 3 < d i s [ v 4 ] = ∞ dis[v_1]+w(u,v)=2+(-5)=-3<dis[v_4]=\infin dis[v1​]+w(u,v)=2+(−5)=−3<dis[v4​]=∞,所以 d i s [ v 4 ] dis[v_4] dis[v4​]被更新为-3。可以发现,即使插入了一些不在最短路径 p p p中的边,并且对这些边松弛后,也不影响最终的结果 d i s [ v 4 ] = δ ( s , v 4 ) = − 3 dis[v_4]=\delta(s,v_4)=-3 dis[v4​]=δ(s,v4​)=−3
  • 栗子三:假设我们按照 v 1 → v 4 , v 0 → v 1 , ⋯   , v 1 → v 4 v_1\to v_4,v_0\to v_1,\cdots ,v_1\to v_4 v1​→v4​,v0​→v1​,⋯,v1​→v4​,那么对 v 1 → v 4 v_1\to v_4 v1​→v4​松弛后, d i s [ v 4 ] + w ( u , v ) = ∞ + ( − 5 ) = ∞ − 5 < d i s [ v 4 ] = ∞ dis[v_4]+w(u,v)=\infin+(-5)=\infin-5<dis[v_4]=\infin dis[v4​]+w(u,v)=∞+(−5)=∞−5<dis[v4​]=∞,所以松弛后, d i s [ v 4 ] dis[v_4] dis[v4​]被更新为 ∞ − 5 \infin -5 ∞−5;那么对 v 0 → v 1 v_0\to v_1 v0​→v1​松弛后, d i s [ v 0 ] + w ( u , v ) = 0 + 2 = 2 < d i s [ v 1 ] = ∞ dis[v_0]+w(u,v)=0+2=2<dis[v_1]=\infin dis[v0​]+w(u,v)=0+2=2<dis[v1​]=∞,所以松弛后, d i s [ v 1 ] dis[v_1] dis[v1​]被更新为2; ⋯ \cdots ⋯;接着对 v 1 → v 4 v_1\to v_4 v1​→v4​松弛后, d i s [ v 1 ] + w ( u , v ) = 2 + ( − 5 ) = − 3 < d i s [ v 4 ] = ∞ dis[v_1]+w(u,v)=2+(-5)=-3<dis[v_4]=\infin dis[v1​]+w(u,v)=2+(−5)=−3<dis[v4​]=∞,所以 d i s [ v 4 ] dis[v_4] dis[v4​]被更新为-3
  • 也就是说,不论在 v 0 → v 1 , v 1 → v 2 , ⋯   , v k − 1 , v k v_0\to v_1,v_1\to v_2,\cdots ,v_{k-1},v_k v0​→v1​,v1​→v2​,⋯,vk−1​,vk​中插入了啥,松弛后,都会有 d i s [ v k ] = δ ( s , v k ) dis[v_k]=\delta (s,v_k) dis[vk​]=δ(s,vk​),这就是路径松弛性质

Bellman_Ford

为什么Bellman_Ford算法最外层最多迭代V-1次,就可以求出源点到其他各点的最短距离呢?

对于BF算法来说,外层循环控制迭代次数,内层循环每次都是对所有边进行松弛。但是对所有边进行松弛,这里所有边的顺序都不一定就是我们想要的按照 v 0 → v 1 , v 1 → v 2 , ⋯   , v k − 1 → v k v_0\to v_1,v_1\to v_2,\cdots ,v_{k-1}\to v_k v0​→v1​,v1​→v2​,⋯,vk−1​→vk​的完美顺序,如果它能直接按照最短路径 p p p的顺序进行松弛,那么就可以很快得出结果。但是,由于我们每一轮,都是对所有边进行松弛,那么第一轮中一定包含 v 0 → v 1 v_0\to v_1 v0​→v1​,第二轮中一定包含 v 1 → v 2 v_1\to v_2 v1​→v2​, ⋯ \cdots ⋯,第 k k k轮中一定包含 v k − 1 → v k v_{k-1}\to v_k vk−1​→vk​,那么结合这么多轮的顺序,每一轮都抽出关键的,然后排列,最终一定会得到我们想要的按照 v 0 → v 1 , v 1 → v 2 , ⋯   , v k − 1 → v k v_0\to v_1,v_1\to v_2,\cdots ,v_{k-1}\to v_k v0​→v1​,v1​→v2​,⋯,vk−1​→vk​的完美顺序。

举个简单的栗子:

设源点 s = v 0 s=v_0 s=v0​,初始化dis数组为 [ 0 , ∞ , ∞ , ∞ , ∞ ] [0,\infin,\infin,\infin,\infin] [0,∞,∞,∞,∞]

Bellman_Ford算法证明

  • 最好的情况:所有边的顺序为 v 0 → v 1 , v 1 → v 2 , v 2 → v 3 , v 3 → v 4 v_0\to v_1,v_1\to v_2,v_2\to v_3,v_3\to v_4 v0​→v1​,v1​→v2​,v2​→v3​,v3​→v4​,迭代1次,进入第一轮后,dis数组变为 [ 0 , 2 , 0 , − 1 , 4 ] [0,2,0,-1,4] [0,2,0,−1,4],即只需要迭代一次,就可以找到了源点 v 0 v_0 v0​的单源最短路径
  • 最坏的情况:所有边的顺序为 v 3 → v 4 , v 2 → v 3 , v 1 → v 2 , v 0 → v 1 v_3\to v_4,v_2\to v_3,v_1\to v_2,v_0\to v_1 v3​→v4​,v2​→v3​,v1​→v2​,v0​→v1​,则需要迭代4次,才能找到源点 v 0 v_0 v0​的单源最短路径
    • 第一轮:松弛 v 3 → v 4 v_3\to v_4 v3​→v4​,由于 d i s [ v 3 ] + w ( v 3 , v 4 ) = ∞ + 5 > d i s [ v 4 ] = ∞ dis[v_3]+w(v_3,v_4)=\infin+5>dis[v_4]=\infin dis[v3​]+w(v3​,v4​)=∞+5>dis[v4​]=∞,所以 v 4 v_4 v4​保持不变。仍为 d i s [ v 4 ] = ∞ dis[v_4]=\infin dis[v4​]=∞;松弛 v 2 → v 3 v_2\to v_3 v2​→v3​,由于 d i s [ v 2 ] + w ( v 2 , v 3 ) = ∞ + ( − 1 ) < d i s [ v 3 ] = ∞ dis[v_2]+w(v_2,v_3)=\infin+(-1)<dis[v_3]=\infin dis[v2​]+w(v2​,v3​)=∞+(−1)<dis[v3​]=∞,所以 v 3 v_3 v3​被更新为 ∞ − 1 \infin-1 ∞−1;松弛 v 1 → v 2 v_1\to v_2 v1​→v2​,由于 d i s [ v 1 ] + w ( v 1 , v 2 ) = ∞ + ( − 2 ) < d i s [ v 2 ] = ∞ dis[v_1]+w(v_1,v_2)=\infin+(-2)<dis[v_2]=\infin dis[v1​]+w(v1​,v2​)=∞+(−2)<dis[v2​]=∞,所以 v 2 v_2 v2​被更新为 ∞ − 2 \infin-2 ∞−2;松弛 v 0 → v 1 v_0\to v_1 v0​→v1​,由于 d i s [ v 0 ] + w ( v 0 , v 1 ) = 0 + 2 < d i s [ v 1 ] = ∞ dis[v_0]+w(v_0,v_1)=0+2<dis[v_1]=\infin dis[v0​]+w(v0​,v1​)=0+2<dis[v1​]=∞,所以 v 1 v_1 v1​被更新为2。所以dis数组变为 [ 0 , 2 , ∞ − 2 , ∞ − 1 , ∞ ] [0,2,\infin-2,\infin-1,\infin] [0,2,∞−2,∞−1,∞],其实在数学中来说,正无穷加或减去一个很小的数,结果仍是正无穷,因此这里 v 3 v_3 v3​被更新为 ∞ − 1 \infin -1 ∞−1其实也可以看作是 ∞ \infin ∞,其他同理。这里只是为了看出松弛操作的结果。所以这里dis数组严格来说其实是 [ 0 , 2 , ∞ , ∞ , ∞ ] [0,2,\infin,\infin,\infin] [0,2,∞,∞,∞]
    • 第二轮:松弛 v 3 → v 4 v_3\to v_4 v3​→v4​,由于 d i s [ v 3 ] + w ( v 3 , v 4 ) = ∞ − 1 + 5 > d i s [ v 4 ] = ∞ dis[v_3]+w(v_3,v_4)=\infin-1+5>dis[v_4]=\infin dis[v3​]+w(v3​,v4​)=∞−1+5>dis[v4​]=∞,所以 v 4 v_4 v4​保持不变。仍为 d i s [ v 4 ] = ∞ dis[v_4]=\infin dis[v4​]=∞;松弛 v 2 → v 3 v_2\to v_3 v2​→v3​,由于 d i s [ v 2 ] + w ( v 2 , v 3 ) = ∞ − 2 + ( − 1 ) < d i s [ v 3 ] = ∞ − 1 dis[v_2]+w(v_2,v_3)=\infin-2+(-1)<dis[v_3]=\infin-1 dis[v2​]+w(v2​,v3​)=∞−2+(−1)<dis[v3​]=∞−1,所以 v 3 v_3 v3​被更新为 ∞ − 2 \infin-2 ∞−2;松弛 v 1 → v 2 v_1\to v_2 v1​→v2​,由于 d i s [ v 1 ] + w ( v 1 , v 2 ) = 2 + ( − 2 ) < d i s [ v 2 ] = ∞ − 2 dis[v_1]+w(v_1,v_2)=2+(-2)<dis[v_2]=\infin-2 dis[v1​]+w(v1​,v2​)=2+(−2)<dis[v2​]=∞−2,所以 v 2 v_2 v2​被更新为 0 0 0;松弛 v 0 → v 1 v_0\to v_1 v0​→v1​,由于 d i s [ v 0 ] + w ( v 0 , v 1 ) = 0 + 2 = = d i s [ v 1 ] = 2 dis[v_0]+w(v_0,v_1)=0+2==dis[v_1]=2 dis[v0​]+w(v0​,v1​)=0+2==dis[v1​]=2,所以 v 1 v_1 v1​不变。所以dis数组变为 [ 0 , 2 , 0 , ∞ − 2 , ∞ ] [0,2,0,\infin-2,\infin] [0,2,0,∞−2,∞]
    • 第三轮:松弛 v 3 → v 4 v_3\to v_4 v3​→v4​,由于 d i s [ v 3 ] + w ( v 3 , v 4 ) = ∞ − 2 + 5 > d i s [ v 4 ] = ∞ dis[v_3]+w(v_3,v_4)=\infin-2+5>dis[v_4]=\infin dis[v3​]+w(v3​,v4​)=∞−2+5>dis[v4​]=∞,所以 v 4 v_4 v4​保持不变。仍为 d i s [ v 4 ] = ∞ dis[v_4]=\infin dis[v4​]=∞;松弛 v 2 → v 3 v_2\to v_3 v2​→v3​,由于 d i s [ v 2 ] + w ( v 2 , v 3 ) = 0 + ( − 1 ) < d i s [ v 3 ] = ∞ − 2 dis[v_2]+w(v_2,v_3)=0+(-1)<dis[v_3]=\infin-2 dis[v2​]+w(v2​,v3​)=0+(−1)<dis[v3​]=∞−2,所以 v 3 v_3 v3​被更新为 − 1 -1 −1;松弛 v 1 → v 2 v_1\to v_2 v1​→v2​,由于 d i s [ v 1 ] + w ( v 1 , v 2 ) = 2 + ( − 2 ) = = i s [ v 2 ] = 0 dis[v_1]+w(v_1,v_2)=2+(-2)==is[v_2]=0 dis[v1​]+w(v1​,v2​)=2+(−2)==is[v2​]=0,所以 v 2 v_2 v2​不变;松弛 v 0 → v 1 v_0\to v_1 v0​→v1​,由于 d i s [ v 0 ] + w ( v 0 , v 1 ) = 0 + 2 = = d i s [ v 1 ] = 2 dis[v_0]+w(v_0,v_1)=0+2==dis[v_1]=2 dis[v0​]+w(v0​,v1​)=0+2==dis[v1​]=2,所以 v 1 v_1 v1​不变。所以dis数组变为 [ 0 , 2 , 0 , − 1 , ∞ ] [0,2,0,-1,\infin] [0,2,0,−1,∞]
    • 第三轮:松弛 v 3 → v 4 v_3\to v_4 v3​→v4​,由于 d i s [ v 3 ] + w ( v 3 , v 4 ) = − 1 + 5 < d i s [ v 4 ] = ∞ dis[v_3]+w(v_3,v_4)=-1+5<dis[v_4]=\infin dis[v3​]+w(v3​,v4​)=−1+5<dis[v4​]=∞,所以 v 4 v_4 v4​被更新为4;松弛 v 2 → v 3 v_2\to v_3 v2​→v3​,由于 d i s [ v 2 ] + w ( v 2 , v 3 ) = 0 + ( − 1 ) = = d i s [ v 3 ] = ∞ − 2 dis[v_2]+w(v_2,v_3)=0+(-1)==dis[v_3]=\infin-2 dis[v2​]+w(v2​,v3​)=0+(−1)==dis[v3​]=∞−2,所以 v 3 v_3 v3​不变;松弛 v 1 → v 2 v_1\to v_2 v1​→v2​,由于 d i s [ v 1 ] + w ( v 1 , v 2 ) = 2 + ( − 2 ) = = i s [ v 2 ] = 0 dis[v_1]+w(v_1,v_2)=2+(-2)==is[v_2]=0 dis[v1​]+w(v1​,v2​)=2+(−2)==is[v2​]=0,所以 v 2 v_2 v2​不变;松弛 v 0 → v 1 v_0\to v_1 v0​→v1​,由于 d i s [ v 0 ] + w ( v 0 , v 1 ) = 0 + 2 = = d i s [ v 1 ] = 2 dis[v_0]+w(v_0,v_1)=0+2==dis[v_1]=2 dis[v0​]+w(v0​,v1​)=0+2==dis[v1​]=2,所以 v 1 v_1 v1​不变。所以dis数组变为 [ 0 , 2 , 0 , − 1 , 4 ] [0,2,0,-1,4] [0,2,0,−1,4]
    • 总结:可以发现,如果按照所有边的顺序为 v 3 → v 4 , v 2 → v 3 , v 1 → v 2 , v 0 → v 1 v_3\to v_4,v_2\to v_3,v_1\to v_2,v_0\to v_1 v3​→v4​,v2​→v3​,v1​→v2​,v0​→v1​,则需要迭代4次,第一轮抽出 v 0 → v 1 v0\to v_1 v0→v1​;第二轮抽出 v 1 → v 2 v_1\to v_2 v1​→v2​;第三轮抽出 v 2 → v 3 v_2\to v_3 v2​→v3​;第四轮抽出 v 3 → v 4 v_3\to v_4 v3​→v4​,那么仍然可以排列成我们想要的顺序 v 0 → v 1 , v 1 → v 2 , v 2 → v 3 , v 3 → v 4 v_0\to v_1,v_1\to v_2,v_2\to v_3,v_3\to v_4 v0​→v1​,v1​→v2​,v2​→v3​,v3​→v4​,但是要得出这个正确的顺序,得需要迭代V-1次。

由于最短路径是简单路径,不含有回路,因此,如果有V各顶点,那么最短路径 p p p最多有V-1条边。也就是说,最坏迭代V-1次,就能找到源点到其他各点的最短距离了

举个复杂的栗子:

设源点 s = v 0 s=v_0 s=v0​,初始化dis数组为 [ 0 , ∞ , ∞ , ∞ , ∞ ] [0,\infin,\infin,\infin,\infin] [0,∞,∞,∞,∞],已 d i s [ v 0 ] = δ ( s , v 0 ) = 0 dis[v_0]=\delta(s,v_0)=0 dis[v0​]=δ(s,v0​)=0。

对于源点 v 0 v_0 v0​到图中其它点的最短路径 p p p,那么 p p p中最少含有1条边,最多含有V-1条边

Bellman_Ford算法证明

Bellman_Ford算法证明

Bellman_Ford算法证明

如何理解第 k k k次迭代中,就找到了经历 k k k条边的最短路径呢?

例如在之前给出的图中,按照所有边的顺序为 v 3 → v 4 , v 2 → v 3 , v 1 → v 2 , v 0 → v 1 v_3\to v_4,v_2\to v_3,v_1\to v_2,v_0\to v_1 v3​→v4​,v2​→v3​,v1​→v2​,v0​→v1​,第一次迭代,抽出 v 0 → v 1 v_0\to v_1 v0​→v1​,得到了起点 v 0 v_0 v0​到节点 v 1 v_1 v1​的最短距离,而 v 0 v_0 v0​到 v 1 v_1 v1​只经过1条边,因此,经过第1次迭代后,我们找到了经历1条边的最短路径 v 0 → v 1 v_0\to v_1 v0​→v1​;第二次迭代,抽出 v 1 → v 2 v_1\to v_2 v1​→v2​,得到了起点 v 0 v_0 v0​到节点 v 2 v_2 v2​的最短距离,而 v 0 v_0 v0​到 v 2 v_2 v2​经历了2条边,因此,经过2次迭代后,我们找到了经历2条边的最短路径 v 0 → v 1 → v 2 v_0\to v_1\to v_2 v0​→v1​→v2​;第三次迭代,抽出 v 2 → v 3 v_2\to v_3 v2​→v3​,得到了起点到节点 v 3 v_3 v3​的最短距离,而 v 0 v_0 v0​到 v 3 v_3 v3​经历了3条边,因此经过3次迭代后,我们找到了经历3条边的最短路径 v 0 → v 1 → v 2 → v 3 v_0\to v_1\to v_2\to v_3 v0​→v1​→v2​→v3​;第四次迭代,抽出 v 3 → v 4 v_3\to v_4 v3​→v4​,得到了起点到节点 v 4 v_4 v4​的最短距离,而 v 0 v_0 v0​到 v 4 v_4 v4​经历了4条边,因此经过4次迭代后,我们找到了经历4条边的最短路径 v 0 → v 1 → v 2 → v 3 → v 4 v_0\to v_1\to v_2\to v_3\to v_4 v0​→v1​→v2​→v3​→v4​;

因此,第 k k k次迭代中,就找到了经历 k k k条边的最短路径。


Bellman_Ford判负环

Bellman_Ford算法证明

Bellman_Ford算法证明

Bellman_Ford算法证明

Bellman_Ford算法证明


上一篇:day16 阶段总结


下一篇:boost::outcome_v2::std_result用法的测试程序