7.6.1 单源最短路径-迪杰斯特拉算法在线视频

同学们，大家好

欢迎回到《数据结构》课堂

这一节课，我们学习最短路径算法

关于最短路径，我们会讨论两个算法

一个是单源最短路径算法

迪杰斯特拉算法

一个是图中任意两个顶点之间最短路径的算法

弗洛伊德算法

先介绍单源最短路径算法

以有向图为例

认识一下从某个源点到其余各顶点的最短路径概念

v0到vi的路径可能有多条

算法的目的是求出其中最短的一条

图中有6个顶点

红圈的v0是源点，单源最短路径就是求

v0到其余各顶点的最短路径，有向图中路径也是有向的

图右部列出了v0到其余各点的最短路径

v0到v1没有路径，v0到v2的最短路径长度是是10

这是一条v0到v2直达的弧

路径中的顶点就是v0,v2，v0到v3的最短路径长度是50

路径经过的顶点是v0,v4,v3。其它2个顶点情况类似

不可能一下求出那么多条最短路径

那么我们按什么样的次序来一条一条求出所有最短路径呢？

我们讨论一下求最短路径的次序

先看图，假设图中是v0到vi的最短路径

这条路径中间经过了vk和vj两个顶点

如果这是从v0到vi的最短路径的话

那么可以肯定，其中v0到vk这一段一定是v0到vk的最短路径

同理，v0到vj这一段，也一定是v0到vj的最短路径

如果不是，比如说从v0到vk有一条更短的路径

那么和假设是矛盾的

从这个例子当中我们可以直观的领会到

如果没有求得v0到vk的最短路径

不可能求得v0到vj的最短路径

同理，没有求得v0到vj的最短路径

不可能求得v0到vi的最短路径

总结一下就是，要求较长的最短路径

必须在已经求得较短的最短路径基础上，才有可能

所以迪杰斯特拉算法的原则是按最短路径长度递增的次序

求取单源最短路径

结合刚才的例子，按这个原则

首先应该求出v0到v2，它长度最短

其次是v0到v4。再其次是v0到v3

然后是v0到v5，最长的是v0到v1长度可以看做无穷

下面我们介绍一下迪杰斯特拉算法的思想

设求顶点v到其余顶点的最短路径

S为已求得最短路径的顶点集

初始的时候，S当中只有一个顶点，就是源点

考虑那么长度最小的最短路径

也就是第1条求出的最短路径，假设是到顶点vj

下一条长度次短的路径假设是到vk，有两种情况

一是有一条弧从v到vk，或者是从v经过vj再到vk

不会经过其它顶点。为什么呢？

如果经过了其它顶点再到vk

那么到其它顶点的最短路径应该更短

下一条长度次短的最短路径就不是到vk的了，和假设矛盾

在更一般的情况下做个总结

下一条最短路径（设其终点为x）或者是弧(v, x)

或者是中间只经过S中的顶点而最后到达顶点x的路径

这样的路径中，除了最后一个顶点x

其它顶点都是S中已经求得最短路径的顶点

说明一下，对直达的弧v到x来说

v是S中的顶点，x是非S中的顶点

直达的弧实际包含在这样的路径中

借助图形说明为什么下一条最短路径

是中间只经过S中的顶点而最后到达顶点x的路径

图中的顶点按照是否求得最短路径分为两个集合

一个是已经求得最短路径的集合S

一个是未求得最短路径的集合V-S

如果下一条最短路径的终点是x

那么v0到x的最短路径是绿色的样子

路径中除了最后顶点x，其它都是S中的顶点

红色虚线路径是错误的，路径中有V-S的顶点y

那么v0到y的路径就小于v0到x的路径

不满足按照最短路径长度递增的次序求最短路径的原则

基于下一条最短路径是中间只经过S中的顶点

而最后到达顶点x的路径这一思路

看一下算法的过程

S为已求得最短路径的顶点集

初始时只有源点v

D的每个分量D[i]记录当前

所找到的从源点v到每个终点

是没有求得最短路径的顶点

中间只经过S中顶点的最短路径的长度

这里同学们要注意，这里所谓的最短路径是

中间只经过S中顶点的最短路径

不一定是最终的最短路径

如果D中记录了所有V-S中顶点这样的路径

根据前面的讨论，下一条最短路径是最小D[i]对应的路径

另外，随着不断按递增次序求得最短路径

新的顶点会加入S，所以D[i]会更新

以保持记录只经过S中顶点的最短路径这个特性

结合有向图的例子看一下算法的过程

观察D初始时情况，初始时S中只有一个源点

图中v0是源点，D中对应v0的位置是0号单元

D[0]=0表示v0是S中的顶点

v1到v5是V-S中没有求得最短路径的顶点

因为S中只有源点，所以D就记录v0到其余顶点直达的弧

v0到v2,v4,v5有弧，D中就在对应单元记录弧的长度

D[2]=10, D[4]=30, D[5]=100, v0到v1,v3没有弧

对应单元记录无穷

D中就记录了目前从源点出发

只经过S中的顶点而到达其余各顶点的最短路径

找到这样路径中最小的D[i]，这里是D[2]

对应的顶点是v2，这是求得的长度最小的一条最短路径

v0到v2的最短路径，路径长度为10

求得这条最短路径以后，把v2加入到S，D[2]置为0

这时S发生了变化，需要考察从v2到其余V-S的顶点是否有弧

有的话就能够构造一条只经过S中的顶点的新路径

如果这条新路径比原来的路径短

则对应的D[i]需要更新，否则保持原来的D[i]

观察图，v2只有一个后继v3

弧长是50，v0到v2的最短路径长度是10

加上弧长50，新路径长度60

原来D[3]中是无穷，更新D[3]=60

v2到其余顶点没有弧

S加入v2后更新的情况如图v2上的D所示

继续求下一条次短的最短路径，D[4]最小

求得v0到v4的最短路径，路径长度为30

把v4加入到S，D[4]置为0

v4有后继v3和v5，到v3的新路径长度是30+20=50

原来D[3]中是60，更新D[3]=50

到v5的新路径长度是30+60=90

原来D[5]中是100，更新D[5]=90

S中加入v4后更新的情况如图v4上的D所示

后续就按照这样步骤依次求出到v3

v5的最短路径是50,60，最后是到v1的无穷

下面看一下算法的描述

第1步，以邻接矩阵存储有向网，初始化D

第2步，选择最小的D[j]

其对应的顶点vj就是下一条求得最短路径的终点

把vj加入到S中

第3步，S中增加了顶点vj

考察从vj到其后继vk（V-S中的顶点）的新路径

是否比原来D[k]中的路径短

如果短用新路径长度对D[k]进行更新，否则D[k]不变

第4步 重复2,3两步n-1次

找出v0到其余n-1个顶点的最短路径

看程序之前，有个问题需要说一下

程序中用到了一个布尔矩阵p

这个矩阵和我们的数组D同步

记录数组D[i]中路径所对应的顶点有那几个

D会变化，p也随之变化

观察图，图1是D初始化的情况

记录的是直达的弧，看一下D[5],这条路径长度是100

是v0到v5的弧，路径的顶点是v0和v5

矩阵p中和这条路径对应的是第5行

第5行中0和5列置1

表示路径中的顶点是v0和v5

同理，第2行描述D[2]的顶点是v0和v2

第4行描述D[4]的顶点是v0和v4

如果D[i]更新了路径，矩阵对应的第i行也要更新

观察图2,D[3]更新为60，那么矩阵的第3行同步更新

路径涉及的顶点有v0,v2和v3

下面看一下实现算法的函数，涉及到三个参数

一个是数组表示法存储的图G

一个整数v0，表示出发点的存储位置

另外就是布尔矩阵p，最后是数组D

第1个for循环是对所有顶点初始化

我们用了一个final数组标记顶点是否在集合S中

初始时所有顶点都不在S中，final[v]置为false

D[v]初始为v0到v直达的弧长

把布尔矩阵第v行全部置为0

如果v0到v有弧，把第v行v0和v列置为1

循环结束后，D[v0]置0; final[v0]赋值TRUE

表示v0是S中的顶点

下面这个for循环要循环n-1次，按长度递增的次序

每次求出一个终点的最短路径

绿色这段代码是用一个循环在D中找出

V-S中顶点的最小的D[w]，循环结束后

v中记录具有最小D[w]的顶点，min记录最小D[w]的值

意思是找到的最短路径终点是v

v0到v的最短路径长度是min

final[v]赋值TRUE，表示v加入S中

黄色这段代码是v加入S后更新D

循环考察每个顶点w，如果w是V-S的顶点

并且到v的路径加v到w弧长小于原来的D[w]

则更新D[w]，同时，更新布尔矩阵中对应w的行

记录新路径对应的顶点

迪杰斯特拉算法主要时间花销是两个嵌套的for循环

算法时间复杂度为O(n2)

好，同学们

迪杰斯特拉算法我们就介绍到这

下次课再见