迪杰斯特拉算法（Dijkstra）证明

男娘i 2022-05-25 04:09 356阅读 0赞

# 首先，这篇文章是在讲《图论》时候写文章 #

（所以，还是以理论为主，以后有空的时候，会把代码发上来，不过我觉得大家看完理论，如果讲得好，代码也就比较容易了。如果讲得不好，网上的代码也是大把，不看这篇文章也罢了）

--------------------

## 任务目标： ##

给个起点S，找到图中每个点距离起点S的最小距离（考虑联通性的问题）。

--------------------

## 算法思路概述 ##

先选第一个距离S最近的点。之后，更新其他图中的点到S的距离。更新原因：**新增加的最近点可以作为一个桥。**

*  输入是：点之间的距离矩阵。
 *  维护是：上面矩阵中的某一行

--------------------

**下图为老师的课件内容部分**，我觉得虽然详尽，但也有些枯燥。可能是为了凝练语言吧。如果有耐心看的话，倒真的是一篇非常好的文章。  
**我在后面会用自己的语言阐述，可能会比较清晰（但废话可能也比较多）。**

**其中前面的黄色部分是我自己标注的（老师写的），后面的黄色部分是我自己写的。**

--------------------

![这里写图片描述][70]

--------------------

## 阐述 ##

1.  首先，选定一个点 v 0 v0 v0，先假设所有的点到某个点的路径都是无穷（当然自己到自己肯定得是长度是0…）。
2.  然后确定一个集合 S S S，这集合表示已经被访问的过点。（那么没有被访问过的点，也是很容易解决的…），这里用个bool数组什么的标记一下吧。
3.  之后，先更新所有点到这个 v 0 v0 v0的距离。怎么更新呢？
4.  所有点通过已经被访问过的点到达 v 0 v0 v0的距离，在结合 d ( v 0 , v i ) = m i n v j ∈ ( S ) ( d ( v 0 , v j ) + w ( v j , v i ) ) d(v0, vi) = min\_\{vj \\in (S)\}(d(v0, vj) + w(vj, vi)) d(v0,vi)=minvj∈(S)(d(v0,vj)\+w(vj,vi)) ( **一般就是新增加的那个点考虑下就好了** )。就是在中间搭一个桥，如果，通过这个桥的点会让这个路变得更近，就更新这个路径的长度。
5.  然后选个最近的点，然后把这个最近的点标记访问过。纳入到集合 S S S
6.  然后，一直到把所有的点都纳入进去之后，就没什么事情了~

这里面，有很多的问题，乍一看都是有点合情合理，但是却让人一下子想不明白的。  
归结到一条，就是，**为什么这样子，就能保证一定会是得到了所有的点，到这个点 v 0 v0 v0的最短距离呢？**

--------------------

## 证明（不严格的证明） ##

1.  **首先，我们能保证，拿到的第一个点，一定是跟 v 0 v0 v0最近的点。** 因为，首先我们选择的是与 v 0 v0 v0直接相连的点中到 v 0 v0 v0最近的点。如果之后的选的方法得到点，有能够得到的点到 v 0 v0 v0的距离小于一开始选的这个点的话，这是不科学的。因为，我们每次选点，都是根据我们维护的一个数组。这个数组的变化过程是，以这个数组中很早就被选中的点的为中转的点，然后，再加上这个中转的点到这个的点的距离，来替代的。**但是，我们知道，任意两点的距离都是大于0的，那么，更新的基本算法是“加法”那么更新之后， 怎么可能得到的数是比之前的数要小呢？**
2.  **同样的道理，第二次被选的点，一定是比以后要选的点都要更近 v 0 v0 v0一点。（最多是相等）。有没有一种感觉，就跟堆排序的方法是一样的。每次，都是把距离 v 0 v0 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时候也是成立的！

**综上所述…**

[70]: /images/20220525/dd71f70e05144191b97460d33d4d9f68.png