这一讲我们介绍Di jkstra算法的正确性。
先看一下它的证明思路。
给出一个命题,算法进行第k步的时候,对于S中的每个结点 i,
相对于S的最短路和它的全局最短路相等。
我们先看看归纳基础,
归纳基础的时候k=1,就是第一步,第一步原点进入了S集合,
原点不管它相对S最短路,还是全局 最短路,长度都是0,因为它没有边,
显然这个等式在第一步是成立的。归纳步骤
是说,假设命题对于k为真,那么对于k+1命题也为真。
下面我们就看看归纳步骤的证明。下面看一下归纳步骤的证明。
假设命题对于k为真,考虑 k+1步算法,这个时候它选择的顶点是v,
这个边呢是u,v边,我们需要证明的是
对于这个k+1步选择的顶点v同样成立,这个等式。
那么假如
到v存在着另外一条路径,从原点出发, 到v有另外一条路径,这条路径
它会从S集合里头跳出来,跳出的 这个顶点是x,从x就跳出S集合
到达了S外面的一个顶点y,然后从y再经过一段路径达到v,
它是这样走的一条路径。下面我们就来看一看
这条路径和算法 选的这条路径,相比之下
是不是算法的路径长度更短,来看一看这个情况。
这是刚才那个图, 我们可以证明,在k+1步的时候,算法是
选的v顶点,这个u,v这条边, 它是这样走的,先经过s中到u的最短路,然后加上u到v
这条边,这是算法选的路径。我们来证明这条路径
一定比其他的路径,像这种路径要比它短。为什么呢?首先
算法在这一步的时候选的是顶点v,没有选y,因为
有一条从s出发相对于x的最短路会到达y,当然这条路径长度应该大于等于
到v的这条相对s最短路的长度。正因为这条长度 比它小,所以算法才选了v顶点,没有选y顶点,
因此我们会得到第一个结果。就是从原点,相对s
到v的最短路长度,要小于等于从原点
经过相对x的最短路到达y的这个相对路的长度,会有这第一个
不等式。然后我们再看一看把这段路的长度
再加上y到v的这条路径长度,才能是
从s到v的这样路径长度,因此这两个加起来 应该不超过全局的长度,就是整个L这条
路径的长度。把这两个公式合到一起, 它小于它,那么这一项应该是大于它的,
因为还加了一项y到v的长度,然后 它又小于L,
把这个不等式综合到一起,我们会得到 dist[v]不超过L,这就说明
这条路径是由s到v的全局 最短路,比其他的路径长度都可能会小。
也就是这个公式成立了。这就说明算法在k+1步
也会得到一个全局的最短路。
下面我们看一下算法的时间复杂度。算法的时间复杂度
是n乘m,因为算法进行了n-1步, 每次挑一个顶点进去,一共挑
n-1个顶点,除了原点之外。那么
在挑的时候要进行dist函数值的更新和比较,
所以要涉及到对边的长度的比较,这个需要O(m)的时间,m是边的
条数,所以整个算法的运行时间是n乘m,这是它的时间复杂度。
如果要采用一个新的数据结构,
基于堆来实现的优先队列的这种数据结构,可以把这个复杂度降下来,降到
m乘以logn的时间。关于这个内容在数据结构课程中
应该做介绍,这里就不再讲了。把贪心法小结一下。
贪心法适合于解决组合优化问题,求解过程
是多步判断过程。最终的判断序列对应于问题的最优解。
判断的时候要依据某种“短视的”贪心选择性质,
短视的意思就是只看眼前。这个贪心性质的选择 决定了算法的正确性,这个选择的方法
往往依赖于直觉或者经验。
贪心法的正确性的证明方法
它一般的是有几种方法。一个是直接计算优化函数,刚好贪心法的解
使得这个函数达到最优值,这是直接的方法。第二种方法就是数学归纳法,可以对
步数归纳,也可以对问题的规模进行归纳。
第三种方法就是交换论证。把一个最优解逐步
转换成算法得到的解,在转换过程中,最优性不降,
就可以通过这样的办法来证明。如果你要证明这个贪心算法不对,
通过举反例就可以了。
对于某些不能保证得到最优解的这样的贪心算法,
可以对它的输入参数做参数化分析,或者是对算法解的
误差做误差的分析。贪心法的优势是算法比较简单,时间
和空间复杂性低。那么我们也介绍了几个著名的贪心算法。
包括最小生成树的Prim算法,最小生成树的 Kruskal算法,以及单源最短路径的Dijkstra
算法。这就是关于贪心法的小结。