多源最短路径Floyd算法的分析与实现

摘要：本文比较详细的介绍了多源最短路径的Floyd算法设计思想，并使用C语言实现了该算法，并对该算法的时间复杂度进行了讨论，在此基础上使用Rational Quantify测试了该算法的实际时间复杂度。
 关键词：最短路径   Floyd算法   算法分析   GIS

Abstract: This paper introduces the thinking of the shortest path’s Floyd in great details, and implements the algorithm with C language. Also, the article analyses the time complexity of the algorithm and tests it with Rational Quantify.
Keywords: shortest path; algorithm Floyd; algorithm analysis; GIS

 1. 引言
 网络分析作为GIS最主要的功能之一，在电子导航、交通旅游、城市规划以及电力、通讯等各种管网、管线的布局设计中发挥了重要的作用，而网络分析中最基本、最关键的问题是最短路径问题。最短路径不仅仅指一般地理意义上的距离最短，还可以引申到其它的度量，如时间、费用、线路容量等等。相应地，最短路径问题就成为最快路径问题、最低费用问题等。对于单源点的最短路径问题，一般采用经典的最短路径算法——Dijkstra算法，只是不同系统对Dijkstra算法采用了不同的实现方法。本文对多源路径算法Floyd算法做了详细的介绍，并编程实现了该算法，最后测试了该算法的性能。
 2. 多源路径Floyd算法思路
 本算法采用邻接矩阵存储图的网络信息，在此用邻接矩阵cost[MAX][MAX]来表示带权有向图，若从Vi到Vj有弧，则cost[i][j]值为弧(Vi，Vj)上的权值，否则为∞。从图的邻接矩阵cost出发，求图中从Vi到Vj的最短路径长度和结点序列。节点图图l的cost矩阵如图2所示。

 如果从Vi到Vj存在弧，则从Vi到Vj存在一条长度为cost「i][j]的路径，该路径不一定是最短路径，尚需进行n次试探。第一次判别(Vi，V1，)和(V1，Vj)，即判别(Vi，V1，Vj)是否存在，若存在，则比较(Vi，Vj)和(Vi，V1，，Vj)路径，取其中最短路径，作为从Vi到Vj的中间顶点不多于一个的最短路径;第二次增加顶点V2，若(Vi……V2)和(V2……Vj)是当前找到的中间结点个数不多于一个的最短路径，则(Vi，……，V2，……，Vj)就有可能是从Vi到Vj的最短路径。将它和已经得到从Vi到Vj的中间顶点不多于一个的最短路径相比较，从中选出长度较短者作为从Vi到Vj的中间顶点不多于二个的最短路径;第三次再增加一个顶点V3，继续进行试探，以此类推。经过n次比较后，最后求得的一定是从Vi到Vj最短路径。按此算法，可以同时求得各对顶点之间的最短路径。
 由上所述，随着试探时内的不断变化，递推地产生一个n×n方阵序A0，A1，A2，……，Ak……，An记录着试探的过程。
 其中:A0 [i] [j] =cost[i] [j]
 Ak[i][j]== min{Ak-1[i][j]，Ak-1[i][k]+Ak-1[k][j]}    1≤k≤n
 在计算公式中，A0[i][j]为初始值，A1[i][j]是从Vi到Vj的中间顶点个数不多于一个的最短路径;Ak[i][j]是从Vi到Vj中间顶点个数不多于K个的最短路径;An[i][j]是从Vi到Vj中间顶点个数不多于n-1个的最短路径;即An[i][j]就是从Vi到Vj的最短路径。在程序中，用数组C[i][j]来存放从顶点Vi到Vj的中间点。
 算法分两部分：第一部分计算出最短路径矩阵An和中间点矩阵C；第二部分根据矩阵An和C求出给定起点到终点的最短路径值和最短路径所经过的中间点。
 
 2.1. 计算最短路径矩阵和中间点矩阵
 
将网络图用表示各顶点间距离dij的相邻矩阵D＝（dij）表达。若图中不存在弧（i，j），则置dij＝M（M为足够大的正数）。dij按下述情况确定：若自顶点i必须经其他点才能回到i，则置dij＝M；否则，置dij＝0。构造中间点矩阵C＝（cij），对所有i，j置cij＝i，以表示此时自顶点i至j的路径均经中间点i。 至k＝0。
第2本步思路是依次以顶点k（k＝1，2，……n）作为中间点，在当前顶点i至j的距离dij和自顶点i经中间点k至j的距离dik＋dkj中，取其小者作为新的最短路长，并将实现此最短路径的中间点k记与cij。由于取最小，故若dik及dkj＝M，则dik＋dkj必步比dij小，故不做。又当i＝k或j＝k时，即经本点时，也不做。
置k＝k+1。对所有dik≠M的i≠k和dkj≠M的j≠k 置dij＝min{dij，dik＋dkj}。若dik＋dkj<dij，则置cij＝k。
第3步：若某dij<0，则存在长为负值的回路，这不可能，故算法中止。若k<n转回2步。算法以k＝n，dij>0终止，此时的dij为所有i至所有j的最短路长。
使用3个嵌套循环语句即可实现迭代过程：（使用一维数组代替二维数组）
 
 2.2. 求出最短路径
 
建立一个含有n个的一维向量p，以存放最短路。K＝1，p[k]＝i，p[k+1]＝j；
构造最短路。将x＝cij，若x≠i且x≠j，说明x是i和j间的中间点，则将p之自n-1至k+1的诸元素依次后移一个标号，并将p[k+1]＝x，j＝x，转回2步，否则k＝k+1。若p[k+1] ≠0，意为最短路尚未构成，则i＝p[k]，j＝p[k+1]，转回2步。否则转3步。
终止。此时p之前k个元素就是最短路上的标号。流程图如下图：
 3. 算法复杂度分析
 考察算法第一部分：即求出最短路径矩阵d和得到中间点矩阵c算法时间复杂度：
 T（n）＝O（n3），
 由于采用邻接矩阵表示，所以空间复杂度为：
 S（n）＝O（n2）
 考虑算法的第二部分：最好的情况是p中的元素不需要移动，即i到j的最短路径就是由i直接到j，此时复杂度为1，最坏的情况是最短路径经过所有的顶点，所以p中的元素移动1+2+3+……n-1次，所以平均时间复杂度为：
 T（n）＝O（n2）
 空间复杂度为：
 S（n）＝O（n）
 所以总的来考虑，该算法的时间复杂度为O（n3），空间复杂度为O（n2）
 由于该算法第一次将所有点对之间的最短路径的值和最短路径的路径信息全部计算出来了，所以第二次在相同网络图形下进行最短路径分析时只需用到算法的第二部分，此时的算法复杂度为O（n2），所以该算法比较适合需要重复计算点对之间的最短路径。重复使用的次数越多，总的时间复杂度越趋近O（n2）。
  4. 算法实现与性能测试
 
 本算法测试采用Rational Quantify工具进行，Quantify是一款面向VB、VC、JAVA的函数级性能分析工具，它可以自动的检测出影响程序运行的性能瓶颈，同时提供图形化的分析表格，帮助程序员进行性能的分析与优化。
 在性能优化的过程中，一些程序员往往是凭着经验去分析自己所写的代码，找到性能瓶颈，这样会面临两个问题：
 （1）程序员所找到的性能瓶颈的代码很可能是自己认为不合理的算法，但在优化的过程中大家都知道性能的优化往往不是优化算法不合理的，而是主要优化占用时间最长的函数；
 （2）在一个大型的项目中，如何在成千上万的代码中找到性能瓶颈是一个最头痛的问题，如果自己不了解所在的项目那就更无法下手。
 Quantify可以高效的发现问题，且不是通过代码的检查来发现问题则是关键，Quantify有以下几个优势：
 ① 对当前的开发影响特别的少，还集成在一些通用的开发工具中，大大的增强了使用的容易度，比如Visual Studio;
 
 ② 性能的显示以图形的方式进行，可以很直接的了解到性能所在的瓶颈；
 ③ 无需源代码就可以对大多数的系统进行性能的分析；
 ④ 同时显示的函数的信息非常的详细，包含了调用的次数，时间等，还有相关的调用关系；
 ⑤ 在测试功能的同时，对性能进行分析，不需要额外的辅助代码；
 本文中为了便于测试，采用随机矩阵进行测试，随机矩阵的对角线元素为零，其他元素是0至1000之间的随机数。本例分别取了N＝{8，16，32，64，128，256，512}测试算法所耗CPU时间。

 测试结果如下表：
 问题规模
（顶点数） 函数Opti耗时
（毫秒） 函数f耗时
（毫秒） 总耗时
（毫秒） 理论耗时
（毫秒）
8 0.0099 0.0003 0.0102 0.0102
     16 0.0856 0.0002 0.0856 0.0816
     32 0.7199 0.0010 0.7209 0.6528
     64 5.8760 0.0011 5.8771 5.2224
     128 47.3333 0.0045 47.3378 41.7792
     256 379.5306 0.0063 379.5306 334.2336
     512 3036.8989 0.0681 3036.9770 2673.8688
 表1：测试结果表

5. 结论
 由测试结果图表可知，随着问题规模的增大，时间耗费以n3的增长，实际测试结果的增长速度略大于理论增长速度，但这种测试方式是理想的；但是有一定的局限性，在设计测试矩阵的时候是考虑了所有点对之间都有边直接相连，而在实际情况中这是很少出现的，尤其是问题规模比较大的时候是不可能出现这种情况的，所以在实际情况中考虑到一个顶点的邻接边数目比较小，时间增长速度应该比理论值小。
 对于函数f在测试过程中耗时总是小的原因，这是因为点和其他任何顶点都相连，所以一般只要经过几个顶点即可达到终点，所以p中需要移动元素的次数比较小，需要判断的次数也比较小。

参考文献
王凌 段江涛 王保保，GIS中最短路径的算法研究与仿真,计算机仿真,
2005（1）：117 - 120.
许志海 魏峰远，交通网络中最短路径算法分析与探讨，河南理工大学学报，2005（1），74 - 78.司连法 王文静，快速Dijkstra最短路径优化算法的 实现，测绘通报，2005（8）:15 - 18.
宋丽敏，最短路径的编程实现，华北航天工业学院学报，2001（11）:25 - 27.
陆 锋，最短路径算法: 分类体系与研究进展[J ]，测绘学报, 2001, 30 (3): 270 - 275.
Benjamin F Zhan. Three Fastest Shortest Path Algorithms on Real Road Networks: Data Structures and Procedures [J]. Journal of Geographic Information and Decision Analysis, 1998, 1 (1), 69 - 82.