7.7.2　求任意一对顶点间的最短路径

上述方法只能求出源点到其他顶点的最短路径，欲求任意一对顶点间的最短路径，可以用每一顶点作为源点，重复调用狄杰斯特拉算法n次，其时间复杂度为O（n3）。下面，我们介绍一种形式更简洁的方法，即弗洛伊德算法，其时间复杂度也是O（n3）。

1.基本思想

对于从vi到vj的弧，进行n次试探：首先考虑路径vi，v0，vj是否存在，如果存在，则比较vi，vj和vi，v0，vj的路径长度，取较短者为从vi到vj的中间顶点的序号不大于0的最短路径。在路径上再增加一个顶点v1，依此类推，在经过n次比较后，最后求得的必是从顶点vi到顶点vj的最短路径。

2.算法示例

算法示例如图7－35所示。

3.算法实现

图的存储结构：带权的邻接矩阵存储结构

数组dist［n］［n］：存放在迭代过程中求得的最短路径长度。迭代公式：

数组path［n］［n］：存放从vi到vj的最短路径，初始为path［i］［j］＝“vivj”。

弗洛伊德算法可以描述如下。

图7－35 算法示例

算法7.11 弗洛伊德算法