Floyd-Warshall算法在现实生活中应用及算法思想引申.docVIP

Floyd-Warshall算法在现实生活中应用及算法思想引申摘要：由一道数学建模题“开封市旅游路线问题”而引发的关于Floyd-Warshall算法求任意两点间最短路径的思考，通过图解描述了算法的核心过程并针对虚拟案例用C++实现，最后做了算法思想的引申思考。 关键字：Floyd-Warshall；最短路径；算法思想引申；旅游路线；APSP 中图分类号：TP311.11 文献标识码：A 文章编号：1007-9599 (2012) 09-0000-02 一、引言 伴随着高科技的日新月异，计算机技术被应用到各个领域，因特网的迅速普及使计算机进一步融入到我们的日常生活中。在这个信息爆炸的e时代，时间显的尤为宝贵，我们不自觉的应用着各种统筹原理和各式各样的“算法”来争取时间，效率至上成了很多个人和组织所追求的意识，就算在旅游休闲时，人们也会想要在有限的资源条件下比别人多赏玩一个“景点”，当然我们追求的不仅仅是多，而且是快。下面就让我们来探讨Floyd-Warshall算法如何帮助我们解决“旅游路线”问题——实现任意两点“最短路径”！ 二、算法描述和图解 Floyd-Warshall算法是图论中的一个算法，专业的讲是寻找给定的带权图或有向网G=（V，E）上每对顶点间最短路径的算法，即APSP(All Pairs Shortest Paths)。该算法运用动态规划思想，框架清晰，不包含复杂数据结构，三重嵌套For循环结构紧凑，易于实现，提高了运算效率，边权可正可负。缺点是时间复杂度较高（O( )），不适合计算大量数据。但对于中等规模的输入图仍然相当实用。 任意两点最短距离有三种情况： （1）两点直达。例如图最短路径：V-X，路径长度：3 （2）通过一个中间点。例如图最短路径：V-X-U，路径长度：7 （3）通过两个及以上点。例如图最短路径：V-X-U-W，路径长度：8 算法过程是用一个矩阵d[][]记录每一对顶点的最短距离，当i等于j时，d[i][j]赋初值为0，当i和j不可达时，d[i][j]赋初值为一个大数，表示无穷。初始化后，依次扫描每一个点，并以其为基点再遍历每一对顶点的权值d[][]，看是否可过该基点让这对顶点间的距离更小。 第一种情况：在初始化的时候已经完成。 第二种情况：对于每一对顶点，遍历所有其它顶点，看是否可以通过一个顶点让这对顶点距离更短，相当于遍历了图中所有的三角形。 第三种情况：如右图的六边形，可先找一点（Y，则=7），右图就变成了五边形问题（V，X，U，W，Z），再找一点（X，则=7），右图就变成了四边形问题（V，U，W，Z），再找一点（U，则=8），右图就变成了三角形（V，W，Z）问题。也就演变成了第二种情况。并且不管先找到哪个点，总可以把n边形问题转化成（n-1）边形问题，最终变成三角形问题。 综合上述三种情况，令 为从顶点i到顶点j且满足所有中间顶点皆属于集合{1，2，…，k}的一条最短路径的权值， 为有向边（i，j）的权，得出如下递归表达式： 三、C++核心代码 #define NUM 100 #define INFINITY 32767 //表示权值的正无穷 typedef struct { char vertex[NUM]； //顶点集 int edges[NUM][NUM]； //存储有向网的邻接矩阵 int vexnum；//点的数目 int arcnum； //弧的数目 }DirectedNet；//有向网 //初始化 void InitializeDN(DirectedNet DN){//输入点数、弧数和点，依照上述“算法过程”进行初始化 } //Floyd算法核心 void Floyd(int distance[][NUM]，int path[][NUM]，DirectedNet DN) { int i，j，k； for (i=0；idistance[i][k]+distance[k][j]) { distance[i][j]=distance[i][k]+distance[k][j]； path[i][j]=k； }//用数组distance[i][j]来记录i，j之间的最短距离，对所有的k值从1到n } //计算distance[i][k]+distance[k][j]的值，修正任意两点之间的最短距离 } //若小于distance[i][j]，则distance[i][j]= distance[i][k]+distance[k][j] } //否则distance[i][j]的值不变。每计算一次都用path[i][j]记录经过的路径点k