当前课程知识点：数据结构 > 第6章 图 > 6.6 最短路径 > 讲解
这一节，我们来学习图的一类很重要的应用，最短路径
我们先来看看最短路径问题
我们给定一个包含若干个顶点、若干条边的图
边上的权值
可能代表顶点之间的距离
假设，我们要求解的是中转次数最少
这时候，我们可以考虑前面介绍的广度优先搜索算法
因为广度优先搜索
最先求出来的解，一定是最近(中转次数最少)的解
但更多时候
我们考虑的，不是中转次数最少
而是距离最短
因为，距离和耗时是成正比的
这时候
我们求解的，也是耗时最少的
这是我们更关心的
那我们就可以采用即将介绍的两种算法，来求最短路径，Dijkstra算法和Floyd算法
我们在这门课当中，主要介绍Dijkstra算法
当然
如果要求中转次数最少
你也可以利用
最短路径算法来求解
比如，我现在将这些距离，全都改成1
这时候，距离最短就退化成了中转次数最少
因为，每经历一个顶点
相当于中转了一次
那距离就是1
现在，我们来看Dijkstra算法
它的算法思想
我们给定
起始顶点v0和终点vd
现在，我们要求一条v0到vd距离最短的路径，注意是距离最短
我们采用的算法思想是，按长度递增次序，逐步产生多条最短路径
直至最短路径到达的终点是vd
换句话说
我们无法(直接)求出给定的
起始顶点v0到目标顶点vd之间的最短路径
我们的算法思想是，先求下一条距离最短的最短路径
我也不知道这条最短路径到达哪个终点
直到我把这条最短路径求出来之后
我才知道它的终点是谁
如果发现它的终点不是给定的vd
这时候，你就再求下一条最短路径
求出来的这多条最短路径
它们的距离(长度)，是依次递增的
这就是Dijkstra算法
它的核心思想
现在，我们来看具体的思想
我们令一个集合S，为已产生的多条最短路径所到达的终点的集合
换句话说
那些求出来的最短路径
它们到达的终点，形成了一个集合
这个集合就是S
比如，S里面有3、4这两个顶点
那说明，v0到v3、v0到v4
这两条最短路径，都已经求出来了
我们把终点放到一个集合S里面，后面会用到它
那么，下一条最短路径呢
假设，它到达的终点是x
现在，有一个非常重要的性质
就是，下一条最短路径
一定仅仅经过S中的某些顶点，而到达x
我们看左边这个图，假设下一条最短路径到达x这个终点
那么，从v0到x
的最短路径
一定只经历S中的某些顶点，而到达x，不会经历不属于S中的顶点
而到达x
我们怎么去证明这个性质呢
很简单
我们用反证法，看右边这个图，假设到达x的最短路径
它经过了不属于S的顶点，比如u
假设，SP
它是从v0开始，经历了
S中的某些顶点
然后，又经历了u顶点，而到达x
注意，这个u，它是不属于S的
我们现在要证明的性质是，下一条最短路径
一定只经历S中的某些顶点
而到达x，也就是没有这一步
现在，假设我们经历了不属于S中的顶点u
我们怎么来证明
它是错的呢
很简单
如果经历了u
那么，这条路径
它的长度，一定是小于
加上这条路径的长度的
现在
红色所标志的路径
它的长度，一定是小于加上u到x这条边的长度的，很明显
因为，这条边的长度是大于0的
现在，v0经过其它的一些顶点，到u的最短路径，是小于这条路径
加上u到x的，说明，u的最短路径已经求出来了
既然u的最短路径已经求出来了
说明u是属于S的
跟我们刚才的这个假设相冲突，u不属于S
所以，下一条最短路径，一定只经历S中的某些顶点
而到达x，绝对不会经历不属于S中的某些顶点，而到达x
现在，我们来看Dijkstra算法
它的具体实现
给定了图G
S初始情况下，仅仅包含给定的起始顶点
v0
为了方便描述
我们引入一个数组D，它的长度
跟顶点个数，是一样的
D[i]这个元素表示
v0到vi的最短路径
后面，我们就不断地迭代D[i]
求出下一条最短路径
如果v0到vi有一条边
那D[i]就初始化成v0到vi
这条边
它的权值，这是初始化D这个数组当中的每一个分量
否则，v0到vi没有边
那就把它初始化成无穷
当然，编程的时候，把它改成一个很大的数，就可以了
重复以下步骤
直到S=V
也就是说，直到v0到其他顶点的最短路径，都求出来了
或者是，v0到给定的vd
你发现求出来的下一条最短路径
它到达的终点是vd
这时候，你也可以停止
下一条最短路径
它是多少呢
所有的D分量的最小值
哪个下标它对应的D元素最小
那么，最短路径就是这个分量
这条最短路径到达的终点，就是vj
注意，我们在找最小值的时候
你应该找不属于S的那些顶点(vj)
它们对应的D[j]
既然下一条最短路径求出来了
它到达的终点是vj
那我们就把vj加到S里面去
表示v0到vj的最短路径，已经求出来了
然后，我们去修改、去迭代之前求出来的D分量，怎么修改呢
把它改成两个数当中的最小值
第一个数
就是当前的D[k]，第二个数
是上一次求出来的最短路径
加上上一次最短路径所到达的终点到vk的边的权值
k是不属于S的
因为要修改所有的D[k]
再说一遍，修改D[k]，修改为当前的D[k]和上一次最短路径D[j]加上vj到vk的这条边它的权值之和
看这二者，谁小一些，就把D[k]修改成谁
刚才我们给出的算法思想比较抽象
不太容易理解
现在，我们通过一个具体的实例
在看完这个实例之后
大家再回到上一页，仔细地理解一下刚才的算法思想
现在，我们给出了每一个分量
以及S，这个S代表当前已求出最短路径所到达的终点的集合，它的初值
仅包含0
因为，0是给定的起始顶点
我们没有给出D[0]这个分量
因为，0是起始顶点
没必要去把它写出来
这4个分量
它们的初值分别是多少呢
很简单，就是0顶点到这些顶点之间
边的权值，如果有，就是权值
如果没有，就是无穷
0到1，有边，是10
为了记录最短路径
经历了哪些顶点
我们在记录这个权值的同时，还给出了这个权值、这个路径
它对应着的顶点序列
比如10，就是0到1
那D[2]又是多少呢
就看0到2，0到2是没有边的
那是无穷，0到3，是30，0到4，是100
现在，我们看这4个分量当中，最小的是谁
是10，它就是我们求出来的第一条最短路径
它到达的终点是1
现在，0到1的最短路径求出来了
我们就把1加到S里面去
然后，去修改剩下的
D分量
因为，顶点1对应的最短路径，已经求出来了
所以，我们没必要再去修改它了
只修改D[2]
D[3]
D[4]
那怎么修改呢
我们就要看两个值，谁小一些
第一个值，是当前分量的值
第二个值，是上一条最短路径D[j]
加上
上一条最短路径到达的终点
和当前的这个顶点
它之间的边的权值
我们看这个
和
这个(应为D[k])
谁小一些
我们就取谁
现在我们看，上一次最短路径到达的终点
1到2有没有边，1到2是有边的
那么，就是50
加上上一条最短路径，是10
那就是60
60是比当前的D[k]要小的
所以，我们把正无穷修改成60
这个60是10加50，也就是0到1
然后，1到2
同样的思想
修改D[3]
我们看，1到3
1到3没有边，那30保留下来
再看，1到4
1到4也没有边
100保留下来
现在，这3个D值，最小的是30
那我们求出来了第2条
最短路径，是30
它到达的终点是3
所以，将3加到S里面去
然后去修改
60和100这两个分量，怎么修改呢
看3到2有没有边，20，加上上一次最短路径30，是等于50的
这个50是小于
当前的60的
所以，把60修改成50
这个50是30加20，30是上一次的最短路径
0到3的30，加上3到2的20
去修改D[4]，3到4
60
加上上一次的30，那是90
小于100
所以，修改成90
现在，两个D分量当中，最小的是50，到达的终点是2
把2加到S里面去
再去修改最后一个分量D[4]
看2到4有没有边，是10
10加上上一次的50，是60，是小于90的
于是，把90改成60
这个60
是上一次的50(0-3-2)
加上2到4之间的10得来的，最后一个D值改完了
它就是最小的
所以，我们求出来的第4条最短路径
它是60
它到达的终点是4
然后，把4加到S里面去
现在，4个顶点的最短路径，都求出来了
这就是Dijkstra算法
它的算法思想，按长度递增
逐渐产生下一条最短路径
这个算法的时间复杂度，很明显是O(n^2)
因为，我们要修改n个D分量
具体来说，是n-1个D分量
在修改n-1个D分量的时候
我们要去遍历其他的D分量
看谁最小
很明显
它的时间复杂度是O(n^2)
本节，我们就讲到这里
下一章，我们将进入查找，同学们，加油！
-讲解
-作业
-讨论1
-讨论2
-1.1 数据结构是什么
--讲解
--作业
-1.2 概念和术语
--讲解
--作业1
--作业2
-1.3 抽象数据类型
--讲解（上）
--讲解（下）
--作业
-1.4 算法及其设计要求
--讲解
--作业
-1.5 算法分析与度量
--讲解（上）
--讲解（下）
--作业1
--作业2
--讨论
-2.1 概念及ADT
--讲解
--作业
-2.2 线性表的顺序实现——顺序表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.3 线性表的链式实现——链表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.4 线性表的应用——多项式
--讲解
--作业
-讨论
-3.1 栈的定义及ADT
--讲解
--作业
-3.2 栈的顺序实现——顺序栈
--讲解
--作业
-3.3 栈的应用
--讲解
--作业
-3.4 栈与递归
--讲解（上）
--讲解（下）
--作业
-3.5 队列的定义及ADT
--讲解
--作业
-3.6 队列的顺序实现——循环队列
--讲解（上）
--讲解（下）
--作业
-讨论
-4.1 数组的定义
--讲解
--作业
-4.2 数组的顺序实现
--讲解
--作业1
--作业2
-4.3 特殊矩阵的压缩存储
--讲解
--作业
-4.4 稀疏矩阵的压缩存储
--讲解（上）
--讲解（下）
--作业
-讨论
-5.1 概念及术语
--讲解
--作业
-5.2 二叉树及其性质
--讲解
--作业1
--作业2
-5.3 二叉树的存储
--讲解
--作业
-5.4 二叉树的遍历及创建
--讲解（上）
--讲解（下）
--作业
-5.5 线索二叉树
--讲解
--作业
-5.6 树与森林
--讲解
--作业
-5.7 Huffman树
--讲解（上）
--讲解（下）
--作业
-讨论
-6.1 概念和术语
--讲解
--作业
-6.2 存储与实现
--讲解（上）
--讲解（下）
--作业
-6.3 遍历
--讲解（上）
--讲解（下）
--作业
-6.4 最小生成树
--讲解（上）
--讲解（下）
--作业1
--作业2
-6.5 拓扑排序
--讲解
--作业
-6.6 最短路径
--讲解
--作业
-讨论
-7.1 概念和术语
--讲解
--作业
-7.2 静态查找表
--讲解（上）
--讲解（下）
--作业
-7.3 二叉排序树
--讲解（上）
--讲解（下）
--作业
-7.4 平衡二叉树
--讲解
--作业
-7.5 哈希表
--讲解（上）
--讲解（下）
--作业
-讨论
-8.1 概念
--讲解
--作业
-8.2 插入排序
--讲解（上）
--讲解（下）
--作业
-8.3 交换排序
--讲解（上）
--讲解（下）
--作业
-8.4 选择排序
--讲解（上）
--讲解（中）
--讲解（下）
--作业
-8.5 归并排序
--讲解
--作业
-讨论
