7.6.2 每一对顶点之间的最短路径-弗洛伊德算法在线视频

同学们大家好

我是云南大学信息学院教师孔兵

这节课我们讨论

每一对顶点之间的最短路径算法，弗洛伊德算法

每一对顶点之间的最短路径算法

目的是要求出，图中任意两点之间的最短路径

基本方法是通过一个二维矩阵迭代

逐步求出每一对顶点之间的最短路径

迭代的初始矩阵，我们称为D-1

D-1是一个矩阵，矩阵中第i行第j列

记录顶点i到顶点j之间直接的路径

如图所示，在有向图中

有3个顶点，v0到v2之间有一条弧

那么D-1中对应的0行2列中记录了

弧长11，v2到v0之间有一条弧

对应的2行0列中记录了弧长3

v2到v1之间没有弧，2行1列中记录无穷

表示没有弧。我们采用数组表示法存储图

D-1可以直接通过描述关系的二维数组赋值获得

D-1可以说是两个顶点之间的直接路径

当然这不一定是最短的路径

这时的路径可称为中间不经过

任意其他顶点的最短路径

注意这个说法

中间不经过任意其它顶点

我们要求出两个顶点之间的最短路径

还需要进行n次试探

试探是通过逐渐加入顶点来实现的

那么，需要确定一个加入顶点试探的次序

就例图来说

假设我们试探是按照v0，v1，v2 的次序来进行

首先加入v0进行试探

加入v0的试探

就是对于任意顶点对vi和vj来说

考察vi到v0，v0到vj的路径长度

如果存在

则比较(vi, vj)和(vi, v0, vj)的路径长度

取长度较短者为从vi到vj的

中间顶点的序号不大于v0的最短路径

结合图例来说明一下

这个试探是在D-1矩阵上进行的

刚才提到过D-1中实际上是记录了

任意两个顶点之间的直达路径

现在，要加入考察的是v0

所以涉及v0的

第0行和第0列的路径就不用考察了

考察vi到v0再到v0

或者是v0到v0再到vi，这样的考察没有意义

需要考察的是v1到v2和v2到v1这两条路径

如图2中两个红圈所示的两条路径

加入v0，先试探v1到v2这条路径

看看v1到v0，v0到v2是否有路径

观察D-1中， v1到v0路径长度为6

v0到v2路径长度11

这条试探的路径长度是17

D-1原来的直达的路径长度是2

原来的较小，保留2为从v1到v2的

中间顶点的序号不大于v0的最短路径

再试探v2到v1这条路径

考察v2到v0，v0到v1是否有路径

v2到v0长度是3，v0到v1

长度是4，这条试探的路径长度是7

D-1原来的直达的路径长度是无穷

取较小的7为从v2到v1的中间顶点的序号

不大于v0的最短路径长度

经过这样的试探更新后

D-1迭代为D0，D的上标0可以理解为

这时的矩阵是加入v0试探后的矩阵

D0被叫做从记录vi到vj

中间顶点序号不大于v0的最短路径矩阵

现在可以这么说了，因为我们加入v0试探过了

这个试探的过程可以持续下去

随后按约定的次序

依次加入v1v2到vn-1进行试探

例如，下一个试探的顶点是v1

考察(vi,..,v1,..,vj)是否存在

如果存在，则将其和已经得到的中间顶点的序号

不大于v0的最短路径相比较

取长度较短者为从vi到vj的中间顶点的序号

不大于v1的最短路径

观察图1，试探是在D0基础上进行的

这个矩阵记录中间顶点序号不大于v0的最短路径长度

现在就是在它的基础上进行试探

加入v1，要试探的是v0到v2，v2到v0这两条路径

先试探v0到v2这条路径

v0到v1中间顶点的序号不大于v0的最短路径长度为4

v1到v2径长度2，这条试探的路径长度是6

D0原来的直达的路径长度是11

这条试探路径的长度较小

取较小的6为从v0到v2的中间顶点的序号

不大于v1的最短路径长度

再试探v2到v0这条路径

v2到v1长度是7，v1到v0

长度是6，这条试探的路径长度是13

D0原来的路径长度是3，保留3

更新后的矩阵叫D1，是加入v1试探后的矩阵

称为从记录vi到vj

中间顶点序号不大于v1的最短路径矩阵

看图2 ，同理在D1的基础上

加入v2进行试探

v0到v2，v2到v1的长度是13

D1中是原来的路径长度是4，保留4

v1到v2，v2到v0的长度是5

D1中是原来的路径长度是是6，更新为5

试探完成后，获得的图3中的D2

D2中实际上就是任意两顶点之间的最短路径

上面，结合图我们讨论了算法的基本思路

下面看一下弗洛伊德算法的算法过程

算法的主要过程是定义一个n阶方阵序列

从D-1，D0到Dn-1

这个序列矩阵就是前面介绍的矩阵D

从D-1开始，通过加入顶点v0, v1

到5.到vn-1试探，获得D0到5.到Dn-1系列矩阵

算法第一步是初始化矩阵D-1

D(-1) [i][j]=arcs[i][j]

把矩阵的i行j列初始化为对应顶点之间直达的弧或边

这是两个顶点之间

中间不经过其它顶点的最短路径

第二步是循环加入v0, v1, 到vn-1进行试探

试探到顶点k时

考察任意两个顶点

加入k的新路径D(k-1) [i][k]+D(k-1) [k][j]

如果新路径小于D(k-1) 中两个顶点的路径D(k-1) [i][j]

则更新

否则

保留原来的D(k-1) [i][j]

D(k-1)中所有路径试探完成后

D(k-1)更新为D(k)

D(k) 中记录任意两个顶点vi到vj

中间顶点序号不大于k的最短路径

迭代最后的矩阵Dn-1中就记录了任意两个顶点之间的最短路径

下面看一下算法的代码实现

弗洛伊德算法涉及到三个参数

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

一个p是三维的布尔矩阵

它的作用和迪杰斯特拉算法中的二维布尔矩阵p是一样的

也是用来标识路径中的顶点有哪些

p和矩阵D中的路径同步

当前矩阵是D(k)的话，p[i][j]对应D(k-1) [i][j]中的路径

第三维具体标识路径中的顶点

标识方式和迪杰斯特拉算法中的一样

第3个参数是最重要的矩阵D

算法开始两个嵌套的for循环

主要是对矩阵D地做初始化

获得矩阵D-1，就是中间不经过任何顶点的最短路径矩阵

同时对三维数组p同步初始化

顶点v和顶点w之间的路径初始化为G.arcs[v][w]

把p[v][w]的第3维初始化为false

如果如果顶点v和顶点w之间有弧

把P[v][w][v]和P[v][w][w]标记为True

表示这条路径当中包含v和w这两个顶点

弗洛伊德算法算法的核心是三个嵌套的for循环

注意

最外层的for循环，k=0.到n-1

这个循环的目的是依次加入顶点0到n-1

每次循环加入一个顶点进行试探

加入的顶点用k表示

内部的两个循环是试探矩阵中所有两个顶点之间的路径

对于顶v到w之间的路径

加入k进行试探

如果v到k

k到w的路径比原来D中的路径小

重置D[v][w]= D[v][k]+D[k][w]

同时，对三维矩阵对应的p[v][w]进行更新

迪杰斯特拉算法是从图中一个顶点出发

求源点到其余各顶点的的最短路径

可以通过n次调用迪杰斯特拉算法

以图中不同顶点为源点

同样可以求得任意两个顶点之间的最大路径

和n次调用迪杰斯特拉算法比较而言

弗洛伊德算法就形式上要简洁一些

就是一个三个循环

弗洛伊德算法的时间复杂度和n次调用

迪杰斯特拉算法是一样

是O(n3)

好，同学们

这节课我们就到这儿

下次课再见