大家好。数据结构与算法这一讲我们继续
第7章图的学习。今天我们学习特别重要的一种
图算法，就是最短路的问题。我们会介绍两种方法。首先我们来看，
单源最短路的这么一个问题。那单源最短路就是对于这么一个
没有负权值的图，那我们给定一个源点，
然后我们要求出从它到其它的所有点的这些最短路的值。
那最短路方法呢，有一个
Dijkstra算法，那它是一个贪心的方法。
那我们把这些元素呢，把它分为两组。
那第一组呢是已经确定了最短路的这些结点，那第二组呢，就是没有确定的这些结点。
那我们每一次呢，我们从这个
已经确定最短路的这个结点来考虑呢，我们找这些
没有确定最短路的这个结点中，它到这个
原点，具有这样的当前最小值的那么一个点。
那我们把这个点呢，扩充进到我们这个已标记的这第一组。
那我们不断的贪心的进行这样的一个方法，那直到所有的
元素都被处理过，或者是有一些不可达的不能够扩展进来为止。那我们来看这样的一组数据。
那首先呢我们是这个原点V0，
那它自己是可达的，而且是它的最短路就是0，其它的都是正无穷。
我们把V0扩展进来以后呢，它
引入的这些连接的点，都具有一个
当前的一个最短路值，但不是最终的那个值。那我们把这个呢，
记录下来。然后我们从我们当前能看到的这些，
还没有进入第一组的这些元素里面，具有最小的Dist值的那个结点，
那我们把它引入到第一组。那这里呢，就是引入了
V2。那引入V2以后呢，它相应的会去修改
它所涉及的这些连接点的Dist值。当然，
有的时候可能是不需要改的，但是我们有的时候是能改的，比如说在
这里，我们把这个V3，原来它是不可达的正无穷，那引入V2以后，
它就变成了，这个值是25。
那我们继续在这个没有进入
第一组的这些元素里面去找Dist值最小的
一个元素。那我们现在引入了V1，
那引入之后，有相应的这些Dist值修改还是没有，我们判断一下。
那不断的去引入这个具有最小Dist的这样的一个顶点，
然后一直到所有的这些可达点都被处理掉。
那我们不可达的这个点呢，它还保留这样的一个
正无穷的最小的路径值。
那我们，这就是刚才这个算法的迭代的过程。
那我们来看一下它相应的算法。
那首先呢，我们是要引入这么一个Dist类。那这里面最重要的就是当前的
最短路长度，以及我们引入这个结点它的那个前驱。
最开始的时候呢，我们进行初始化，把每一个顶点都标记为还没有被访问过，
而且，它的这个Dist值就是正无穷，
它的这样的一个前驱呢，我们假设都是那个
原点。然后呢我们把这样的原点的Dist这样的值呢，
设为0，我插入到这么一个
还没有元素的一个堆里面，那就是目前堆里面只有这个原点，这一个顶点元素。
那我们现在是进行n次的循环操作。
那也就是说，我每一次呢，希望得到一个还没有处理的这个第二组元素，
然后我得到这个元素呢，它是具有最小的这个Dist值，我不断的
引入到第一组。那如果整个这个图都是可达的，那就是正好处理n次，
那如果有不可达的顶点的话呢，在这个算法中间会退出，然后把那些不可达的点呢，
它的Dist值，还是保留为正无穷。那我们首先呢看一下，
如果是这个堆呢，它不空，
那我们从堆顶呢，就删除最小的那个元素。
然后我们判断一下，这个元素呢，它
这个顶点是不是被访问了，如果是没有被访问呢，
我们就退出这个从堆里面找最小的这个工作。
那如果是，这个元素是，已经被访问过，那我继续找最小。
那这里呢其实是，因为我们后面的算法引起的，我们一会再解释。
那如果是说我们在这样的一个
找最小的过程中，我们没找到合适的这个最小的，
那也是说，这个堆为空了，我们还找不到，
那这个时候呢，其实就是有些点是不可达的，我们还没有处理到n次，也就是说，不是每个顶点
都曾经被拿出来，作为这个最小距离的那个候选的项。
那这个时候就是有不可达的，我们让它保留这个
不可达的这种值。我们就退出整个算法。那如果我们找到了，
那这个时候呢，我们把这个找到的这个顶点标记为已经访问了，
加入了这个具有当前最短路Dist的这样的一个顶点v以后，我们看
v所发出来的那些边，涉及到的这些顶点。
那如果这个顶点它的这个原来的这个
最短路值它还大于我们这个v到s的最短路，再加上
这个v到这个顶点的这条边，那也就是说，可以看作是
两边之和要小于这个第三边，这是原来的这样的一个最短路的值。
那我们就用，引入了这个v之后，再引入这条边
的这么一个最短路呢，来替代它原来存的这个临时量。
同时我们要把这个前驱修改为v。那这个时候呢，
我们把这个具有更小的最短路的这个值呢，
插入到堆里面去。那这里面我们要注意，
我并没有删除这个点对应的那个Dist值在堆里面的原来的那个
旧的值，而是把一个更小的新值呢，直接插入。
那这个是没有问题的，因为我们将来
如果这个对应的点，它被作为最小，
作为当前最小来取出来的时候呢，那它呢，
是没有被访问的，它一定是比那个旧值
在前面取出来。而如果那个旧值，它被取出来的时候呢，
那一般我们这里有一个判断，就是说我们要判断，
这个旧值它对应的那个顶点，
是不是被访问过。那因为前面它那个更小的值已经
被取出来被访问过，所以呢，这里它就会对这个旧值呢，就会直接的抛弃。
那我们通过这样的一个处理呢，使得我们不需要
总是去修改旧值，再去插入新值这样的一个过程。
那我们看一下Dijkstra算法它的时间代价。那我们每次呢，
主要就是改变相应的这样的一个顶点它的一个Dist距离。那我们不删除旧值，只是添加新值。
那在最差情况下呢，可能这个堆里面的元素个数会达到
有这个边数那么多个，所以这种操作呢，它的代价会是log(|E|)的，
因为我们要调整堆，那因此我们的整个代价是
Θ((|V|+|E|)log(|E|))。
这样的代价。那对于图算法，我们都需要回答这些问题。
那Dijkstra算法呢，它是针对有向图的，但是无向图也没关系。
然后对于这种非连通图，还有带有回路的都没有问题。
那有问题呢就是，它对于负权图，是不能很好支持的。
那我们看一下，如果是有这么一个负权的环的情况，那我们的这样的
权值呢，就是它的这个最短路呢会出现这个负无穷的情况。
那如果是不存在这个负的回路，但是呢，
在这个处理的过程中，有那个后效性，所以不能够正确处理，比如说，
我们A到C，那因为它的这个权值是6，
它比A到B要小，所以我们根据前面这个单元最短路的方法，
它得到的这样的一个最短路呢C，就是6，它不需要再去重新计算。
但是呢因为有负值的出现，那通过这个AB到
BC，那得到的这个最短路呢是2，就比刚才
AC呢是要小。那这就是一个有后效性的情况。那我们知道，
对于动态规划法呢，它需要支持的是
最优子结构重复值结构及无后效性这几种情况。
那贪心法是动态规划的特例，
那它也必须要遵循无后效性。那因此呢，
对于负权值Dijkstra算法呢，是不能够很好处理的。
有一些方法可以处理这种带负权值的情况，
那大家可以去查阅。那我们再来看一下每对结点间的最短路。
那是不是还能够用前面介绍的单元最短路的这样的算法呢？
当然是可以的。我对每个结点呢，我们都作为原点，
然后调用n次，就可以了。那这里呢，我们介绍一下Floyd的算法。
这是一个非常经典的动态规划法。
那它的这个思想呢，就是我首先呢，
初始化这样的一个相邻矩阵，这个相邻矩阵里面呢，
这些相应的i,j之间的值呢，就是表示它们的
边的这个权值。然后，我对这个矩阵呢做n次
迭代，每一次呢都是拿一个结点作为中间的跳转点来看，
它是不是能够修改前一轮得到的这样的一个i,j之间的最短路。
那经过n次呢，所有的顶点都作为中间跳转点
考虑以后，那整个这个算法就得到了每对结点之间的最短路。
那我们来看下，对最短路的这个组合情况。
那一种情况我可能是，在
第k次迭代的时候呢，我们得到的这么一个矩阵。
那就是在，在第k次迭代的时候呢，我们是基于前面k减1，
那些迭代所得到的矩阵。
那这个时候我们如果是得到的这个最短路的这个
情况呢，我们是加入了Vk作为中间跳转点。那
其实呢，我们可能不需要经过这个Vk作为中间
跳转点，那么就是还保留了上一次的那个最短路的这个情况。
那还有种情况呢，是加入了这个Vk作为中间跳转点。
那我们这个时候呢，就是相当于就是
i,k之间的这个最短路，再加上k,j之间的最短路，
它小于原来这个i,j之间的最短路，所以我们用它来替代，
也就是这样的一个过程。那我们看一下
这个图示。那初始的这个矩阵呢，是这样的。
0行0列还有这个斜对线呢，它是不需要进行操作的。
那我们看到呢，对于这个
V2,V1的这个情况，就是引入了这个
V0点以后，我们可以改善这个V2到V1的最短路。原来
是正无穷，也就是没有直接边可达。那现在呢我们变成了长度为7的这样的一个最短路。
那我们引入了这个V1结点以后，也是类似的一个情况，
那我们也是能够修改这个
V0到V2的这样的一个距离。
那接着再引入V2，那我们
引入了以后呢，我们再来看它的这个最短路的修改。我们这里是能够修改
V1到V0的这样的一个最短路，把原来
是6呢，变成了5。那我们所有的顶点都考虑进来以后呢，
整个这个图，它的两两之间的最短路都已经求得了，而且
它的相应的这样的一个前驱的路径呢，我们也保留了。
那我们看一下这个算法本身。那首先呢就是，初始化的一些操作。
那我们把这个i到i之间的这个
最短路呢设为0，而且它的pre呢就是自己。
然后呢，如果它们不是，就是
同一个这个起始点和终结点，那
也就是i,j不等的情况下呢，我们先把这些
它的最短路呢设为正无穷，而且呢，它的pre呢都设为-1.
然后呢，我们再把这个边的信息，都考虑进去，
就是把那些直接有边相连的，我把这个最短路呢就设为这个直接的边。
然后我们加入新结点之后，我们来更新那些变短的路径长度。
那对于这个新结点呢，我们是考虑整个这个结点集
里面的每一个结点都来作为新结点来考虑一次。
然后呢我们对这个原来图里面的这个i,j结点，
都逐一的来看，那就是对整个这个相邻矩阵呢逐一来看。
那看一下，是不是加入这个新结点之后，它引入的这样的最短路。
那这两段最短路呢，能够小于
原来没有加入之前似乎更直接一些的
这样的i,j之间的这个最短路。如果是，也就是两边
之和小于第三边的时候，那我们就把这个最短路呢，
修改为这个两边之和，这个边我们说的其实是一个子路径了。然后呢，它的这个前驱呢，
我们要设为这个Vj所保留的那样一个前驱。
那Floyd算法它的时间复杂度，
很明显是一个三重循环，它的复杂度是Θ(n^3)的。
那给大家留几个思考。首先呢，就是单元最短路，我们找最小的时候呢，是采用的
最小堆。那如果不是用最小堆，而是在这个Dist数组里面呢，一个一层循环
这样子看下去找最小。那我们效率呢是怎么样的。
提示一下，就是大家可以从稀疏图和密集图的角度来讨论这两种处理方法。
那还有呢，就是Floyd算法，它保留
这个前驱pre的形式，我们是采用的
前一种形式。那如果我们改为就是当前
引入这样的一个最小的，或者说当前的一个最小
是，引入它的是这个v，
那我们如果把这个pre呢，保存为v，那是怎么样的。那
是不是可以，那显然还是可以的，因为它也不影响这个length的求值。
而且呢，我们其实也都能够恢复这样的一个最短路经。
但是呢，在恢复的时候，这两种方法，它的效率是
不一样的。大家可以仔细想一想，这两种算法哪一种更优。
谢谢大家。