社区微信群开通啦,扫一扫抢先加入社区官方微信群
社区微信群
(所以,还是以理论为主,以后有空的时候,会把代码发上来,不过我觉得大家看完理论,如果讲得好,代码也就比较容易了。如果讲得不好,网上的代码也是大把,不看这篇文章也罢了)
给个起点S,找到图中每个点距离起点S的最小距离(考虑联通性的问题)。
先选第一个距离S最近的点。之后,更新其他图中的点到S的距离。更新原因:新增加的最近点可以作为一个桥。
下图为老师的课件内容部分,我觉得虽然详尽,但也有些枯燥。可能是为了凝练语言吧。如果有耐心看的话,倒真的是一篇非常好的文章。
我在后面会用自己的语言阐述,可能会比较清晰(但废话可能也比较多)。
其中前面的黄色部分是我自己标注的(老师写的),后面的黄色部分是我自己写的。
这里面,有很多的问题,乍一看都是有点合情合理,但是却让人一下子想不明白的。
归结到一条,就是,为什么这样子,就能保证一定会是得到了所有的点,到这个点
v
0
v0
v0的最短距离呢?
通过归纳法
(1)
i
=
0
i = 0
i=0
首先,还是一样,根据上面的方式,来依次产生出这些点。这是一个序列,称其为
V
=
v
0
,
v
1
,
v
2
,
.
.
.
.
,
v
n
V= {v0, v1, v2, ....,vn}
V=v0,v1,v2,....,vn这n个点。
v
i
vi
vi对应的距离就是
d
i
di
di。
(2) 设 i < = k i <= k i<=k时成立,下面看 i = k + 1 i = k + 1 i=k+1的情况
v
i
vi
vi通过上述方法生成的点,所得到的到
v
0
v0
v0的距离不是最近的,也就是说,还存在一条路,使得
v
i
vi
vi到
v
0
v0
v0的距离小于
d
i
di
di。
由于,
d
i
di
di的产生方法,我们可以知道,这样的点,必定通过了后面的点(
v
i
>
=
k
+
2
v_{i >= k + 2}
vi>=k+2)。但是,我们同样知道
v
i
>
=
k
+
2
v_{i >= k + 2}
vi>=k+2到
v
0
v0
v0的距离一定是会大于
v
i
<
=
k
v_{i <= k }
vi<=k的。(递增的特点)。所以,只要是通过了后面的点,到达
v
0
v0
v0的距离,一定是大于等于,我们只通过前面的点
v
i
<
=
k
v_{i <= k }
vi<=k到达所致的。但是,这与我们之前的假设有矛盾。这样我们就知道了,
i
=
k
+
1
i = k + 1
i=k+1时候也是成立的!
综上所述…
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!