带权图中任意两点间最短路径的Floyd算法优化

【摘 要】本文首先从传统的Floyd算法的机理入手，详细描述了带权有向图中任意两点之间的最短路径求解过程，通过手工模拟构造排序矩阵和C语言编程实现，找出影响算法效率的关键步骤。

【关键词】Floyd最短路径算法 手工模拟 语句频度 优化算法

最短路径的求解算法通常都依赖于一种性质，即任意两点之间的最短路径，总是也包含了路径上其他顶点间的最短路径。带权有向图G的最短路径问题，一般可分为两类：一是单源最短路径，它是指求一个网络图中任意一个顶点到其他各顶点之间的最短路径，目前比较流行的算法是Dijkstra算法[1]。二是求带权网络图中任意一对顶点间的最短路径，常常选用Floyd-Warshall算法[2]。除了以上两种算法之外，目前国内外对最短路径的算法的研究还有A*算法[3]和Bellman-Ford算法[3]等。Dijkstra算法和Floyd算法各有优缺点[4]，尽管Dijkstra算法属于单源最短路径算法，但也可以用它来解决每对顶点之间的最短路径问题，每一次执行其算法过程时，轮流将一个顶点作为源点即可求出任意两点之间的最短路径，算法的时间复杂度为O（n3）。但该算法的缺点是网络中的边不能带有负权值，否则Dijkstra算法将不再适用。Floyd算法给出了一个解决带权图中任意两点之间最短路径问题的一个新方法。Floyd算法的C语言描述如下：

void Floyd（MGraph G，DistanceMatrix &D）

for（i=0；i

for（j=0；j

A[i][j]=A.arcs[i][j]； //语句3

for（u=0；u

for（i=0；i

for（j=0；j

if（A[i][u]+A[u][j]

A[i][j]=A[i][u]+A[u][j]； //语句8

在该算法中，MGraph是图的邻接矩阵存储结构体类型，DistanceMatrix是距离矩阵二维数组类型。该算法的语句执行频度为n3+n2，时间复杂度为O（n3）。很明显，该算法的缺陷是时间开销是关于顶点的多项式函数，跟图中是否存在边没有关系。下面举例说明该算法的执行过程。例：设图G=（V，E），V={v0，v1，v2}，E={，，，，}。传统Floyd算法的执行过程如表1所示。为了更加详细的说明矩阵中的元素值是如何计算出来的，现在用手工模拟的方法来实现矩阵A（0）。同理，矩阵A（1）和矩阵A（2）求解方法也是完全相同的。在传统的Floyd算法中，在计算vi和vj之间的最短路径时每次都会有n次加法运算，并且大多数时候插入的中间节点vk并不能使原来的路径长度变小，这导致产生了很多没必要的运算过程，降低了计算的效率。鉴于以上缺陷，本文在降低计算次数的基础上对传统的Floyd算法进行优化，从而降低算法的计算量，提高运行效率。 Floyd优化新算法的设计。新的Floyd算法的设计目的主要是为了降低传统算法中的冗余语句处理过程，观察上文中的传统Floyd算法的C语言程序，发现影响整个程序的运行效率的关键语句是“语句7”。在该语句中，不论A[i][u]或A[u][j]在进行加法运算之前是否已经小于A[i][j]，该加法运算总是要执行的。显然在该if语句中，总共要经过2次计算，一次加法计算和一次比较计算。虽然表面上看起来运算次数并不多，但是由于外面套有三层执行次数各为顶点数n的for循环计算，这将会导致该条if语句会被无条件的执行n3次，则需要计算的总次数为2n3次。显然这是十分降低时间效率的行为，原因是A[i][u]和A[u][j]在进行加法计算之前其中的某一个值已经大于或等于A[i][j]的值了，此时仅仅只需要做一次比较运算即可，不需要再额外进行一次加法计算。算法优化的基本思想是：对于迭代矩阵A（k），在计算两点vi和vj之间的最短路径时，对待插入的节点vu先进行路长比较，如果或，则说明插入节点vu之后，点vi途经vu到达vj的路程并不比原来从vi到vj的短，从而就不再需要计算vi，vu，vj这三点的路径之和，从而极大地降低了算法的实际计算量，提高了时间效率。那么，对于经过优化的Floyd算法而言新的描述为：定义一个n阶方阵序列A（-1），A（0），A（1），...，A（n-1），其中k=0，1，2，...，n-1：

A（-1）[i][j]=arcs[i][j]

当A（k-1）[i][u]≥A（k-1）[i][j]或者A（k-1）[u][j]≥A（k-1）[i][j]时，有A（k）[i][j]=A（k-1）[i][j]

A（k）[i][j]=A（k-1）[i][u]+A（k-1）[u][j]

算法步骤中的（2）和（3）这两者只执行一个，当（2）满足时就会跳过（3）然后继续执行；当（2）不满足时就会执行（3）然后继续执行。为了更加直观的描述新算法的执行过程，用实际的编程语言来实现算法的操作。

结论：综上可知，优化之后的Floyd算法在关键语句的执行频度方面为n3+m，远远小于传统的Floyd算法的执行频度2n3。

参考文献：

[1]孙强，Dijkstra的一种改进算法[J].计算机工程与应用，2003，39（3）：99-101.

[2]Thomas H.Cormen、Charles E.Leiserson、Ronald L.Rivest、Clifford Stein.算法导论[M].北京：机械工业出版社.2006：386-390

作者简介：

刘莹，女，1992.6月，回族，本科学历，专业方向：信息与计算科学。