多源最短路径Floyd算法的分析及实现.doc

多源最短路径Floyd算法分析与实现Email:zhouyuqing214@126.com 摘要：本文比较详细的介绍了多源最短路径的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。 本步思路是依次以顶点k（k＝1，2，……n）作为中间点，在当前顶点i至j的距离dij和自顶点i经中间点k至j的距离dik＋dkj中，取其小者作为新的最短路长，并将实现此最短路径的中间点k记与cij。由于取最小，故若dik及dkj＝M，则dik＋dk