在最短路径问题中,我们给定一个带权重的有向图
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∑kw(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
如何理解任何一条路径呢?
最短路径不是唯一的,有很多条最短路径,也就是说会有很多最短路径
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)
证明如下:
负权和负环
负权:图中某些边的权值为负数
负环:存在一个环,这个环中所有边权之和为负数
为什么最短路径中不能存在负权环和正权环呢?
不能存在负权环。如上图,我们想要求从
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)只是设想的最优解
如何理解松弛后一定有
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)
相关性质
路径松弛性质
如果路径
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),再由上界性质,其值之后都不会发生变化,该式子以后恒成立
假设
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
栗子一:假设我们按照
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,∞,∞,∞,∞]
最好的情况:所有边的顺序为
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条边
如何理解第
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;