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
本算法测试采用Rational Quantify工具进行,Quantify是一款面向VB、VC、JAVA的函数级性能分析工具,它可以自动的检测出影响程序运行的性能瓶颈,同时提供图形化的分析表格,帮助程序员进行性能的分析与优化。
在性能优化的过程中,一些程序员往往是凭着经验去分析自己所写的代码,找到性能瓶颈,这样会面临两个问题:
(1)程序员所找到的性能瓶颈的代码很可能是自己认为不合理的算法,但在优化的过程中大家都知道性能的优化往往不是优化算法不合理的,而是主要优化占用时间最长的函数;
(2)在一个大型的项目中,如何在成千上万的代码中找到性能瓶颈是一个最头痛的问题,如果自己不了解所在的项目那就更无法下手。
Quantify可以高效的发现问题,且不是通过代码的检查来发现问题则是关键,Quantify有以下几个优势:
① 对当前的开发影响特别的少,还集成在一些通用的开发工具中,大大的增强了使用的容易度,比如Visual Studio;
② 性能的显示以图形的方式进行,可以很直接的了解到性能所在的瓶颈;
③ 无需源代码就可以对大多数的系统进行性能的分析;
④ 同时显示的函数的信息非常的详细,包含了调用的次数,时间等,还有相关的调用关系;
⑤ 在测试功能的同时,对性能进行分析,不需要额外的辅助代码;
本文中为了便于测试,采用随机矩阵进行测试,随机矩阵的对角线元素为零,其他元素是0至1000之间的随机数。本例分别取了N={8,16,32,64,128,256,512}测试算法所耗CPU时间。