完整版最短路径问题的程序实测.docVIP

(完整版)最短路径问题的程序实测

(完整版)最短路径问题的程序实测

(完整版)最短路径问题的程序实测

最短路径问题的程序实测

5。1测试目的

测试堆实现的基于Dijkstra的最短路算法与数组实现的基于Dijkstra的最短路算法的异同与优劣.

5。2测试内容

第一阶段测试系统基本性能，第二阶段测试系统可能出现的逻辑错误；本程序的测试数据由程序自动生成。

5。3系统测试程序

测试程序：

使用第四章所展示的程序。

随机有向图生成程序：

closeall；clearall;clc；

length_num=20;

sort_num=10;

range_num=100；

S=ceil（sort_num*rand(1,length_num））；

E=zeros(1,length_num）；

W=ceil（range_num*rand（1，length_num)）；

fori=1：length_num

ifS（1,i）==1

E(1，i）=S（1，i)+1;

elseifS（1,i）==sort_num;

E(1,i)=S(1,i)-1;

else

E(1,i)=S(1，i）+1;

end

end

G=sparse（S，E，W);

G（sort_num，sort_num）=0；

P=biograph（G，[］,ShowWeights’,on);

H=view（P);

测试结果：

以下测试结果均为程序运行100次后的平均总耗时，耗时计算由matlab自带的程序包完成，图片中的红色划线部分表示不同程序中的Dijkstra算法所耗时间；

交通图中测试节点少于10个时的程序平均耗时:

数组实现的最短路算法：

堆实现的最短路算法：

可以看到,当交通图中的顶点数目小于10时,基于Dijkstra算法的最短路问题使用数组解更加快捷；当交通图中的顶点数目小于10时，数组解法地效率是堆算法效率的4倍左右；

交通图中测试节点数目位于990与1000之间时的程序平均耗时:

数组实现的最短路算法:

堆实现的最短路算法：

可以看到，当交通图中的顶点数目大于990小于1000时，基于Dijkstra算法的最短路问题使用最小堆解更加快捷；当交通图中的顶点数目大于990小于1000时，堆算法效率是数组解法地效率的8倍左右；

综上所述，针对最短路问题。当交通图中的节点较少时，数组解法比最小堆解法更有优势；当交通图中的节点较多时，最小堆解法比数组解法更有优势。

HYPERLINK系统总结与展望

系统总结：

在毕业季的我经过几个月的努力,终于完成了毕业设计。在这段时间内，最重要的不是我的知识量比之从前有了显著的提升，最重要的是我的实际应用能力比之以前有了天壤之别。

在这篇文章中所用到的程序使用matlab2012b编写.

系统展望:

在这篇文章中展示的程序虽然满足了我最初的构思，但还是有些地方可以更加尽善尽美.

在本文的操作中，我使用随机生成的交通图作为测试数据。随机生成的数据不会考虑合理性，会产生一些明显不需要计算最短路径的交通图，如：

对于这种一字排开型交通图，在实际生活中计算最短路问题的意义并不大，但是限定程序生成具有几百个顶点的复杂交通图比较复杂,因为时间的原因我并没有研究。如果能将随机复杂交通图的结果与随机简单交通图的结果作一对比，相信本文的研究会更加有说服力。

余生而有涯而学无涯，希望在将来的学习生活中，我可以不断提高自己，面对新的困难时可以不断想办法解决，不负我之所学!